数据结构习题解析与实验指导第六章(图)课后算法设计题

1.分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：

（1）增加一个新顶点$v$, InsertVex(G, v);

（2）删除顶点$v$及其相关的边，DeleteVex(G, v);

（3）增加一条边<v, w>，InsertArc(G, v, w);

（4）删除一条边<v, w>, DeleteArc(G, v, w)。

邻接矩阵(有向图) #include <iostream> using namespace std; struct Graph { static const int MAX_V = 100; int weight[MAX_V][MAX_V]; int vertex[MAX_V]; int size = 0; Graph() { } }; int locate(Graph& graph, int v) { //查找顶点位置 for (int i = 0; i < graph.size; i++) { if (graph.vertex[i] == v) { return i; } } return -1; } void insertVetex(Graph& graph, int v) { if (graph.size + 1 > graph.MAX_V ) { ///如果顶点个数已满 return; } if (locate(graph, v) != -1) { //如果已经存在相同的顶点 return; } graph.vertex[graph.size] = v; for (int i = 0; i <= graph.size; i++) { graph.weight[i][graph.size] = graph.weight[graph.size][i] = 0; } graph.size++; } void insertEdge(Graph& graph, int v, int w) { int i = locate(graph, v); int j = locate(graph, w); if (i != -1 && j != -1) { graph.weight[i][j] = 1; } } void deleteEdge(Graph& graph, int v, int w) { int i = locate(graph, v); int j = locate(graph, w); if (i != -1 && j != -1) { graph.weight[i][j] = 0; } } void deleteVetex(Graph& graph, int v) { int pos = locate(graph, v); int lst = graph.size - 1; if (pos != -1) { //与最后一个顶点交换 int temp = graph.vertex[pos]; graph.vertex[pos] = graph.vertex[lst]; graph.vertex[lst] = temp; for (int i = 0; i < graph.size; i++) { int t = graph.weight[pos][i]; graph.weight[pos][i] = graph.weight[lst][i]; graph.weight[lst][i] = t; } for (int i = 0; i < graph.size; i++) { int t = graph.weight[i][pos]; graph.weight[i][pos] = graph.weight[i][lst]; graph.weight[i][lst] = t; } //删除最后一个顶点 graph.size--; } } void display(Graph& graph){ cout << "vetices: "; for (int i = 0; i < graph.size; i++) { cout << graph.vertex[i] << " "; } cout << endl; cout << "edges: " << endl; for (int i = 0; i < graph.size; i++) { for (int j = 0; j < graph.size; j++) { cout << graph.weight[i][j] << " "; } cout << endl; } } int main() { Graph graph; insertVetex(graph, 4); insertVetex(graph, 5); insertEdge(graph, 5, 4); insertVetex(graph, 5); insertVetex(graph, 6); insertVetex(graph, 7); insertVetex(graph, 8); insertEdge(graph, 4, 6); insertEdge(graph, 3, 6); insertEdge(graph, 7, 7); insertEdge(graph, 7, 8); insertEdge(graph, 8, 7); display(graph); deleteEdge(graph, 4, 6); display(graph); deleteVetex(graph, 5); display(graph); return 0; }

邻接表(有向图) #include <iostream> using namespace std; struct Node { int name; //结点的id, 其实可以用string替代 int weight; //边或结点的权重，在此例用没有用到 Node* next_e; //下一条边 Node* next_v; //下一个顶点 Node(int name = 0, int weight = 0, Node* next_e = 0, Node* next_v = 0) : name(name), weight(weight), next_e(next_e), next_v(next_v) { } }; Node* locate(Node& graph, int v) { //根据id查找顶点 Node* pos = graph.next_v; while (pos != 0) { if (pos->name == v) { return pos; } pos = pos->next_v; } return 0; } void insertVertex(Node& graph, int v) { if (locate(graph, v) == 0) { Node* node = &graph; while (node->next_v != 0) //这里使用后插法 { node = node->next_v; } node->next_v = new Node(v); } } void deleteVertex(Node& graph, int v) { Node* node = &graph; while (node->next_v != 0) { if (node->next_v->name == v) { Node* n = node->next_v; while (n->next_e != 0) { Node* t = n->next_e; n->next_e = n->next_e->next_e; delete t; } Node* temp = node->next_v;; node->next_v = node->next_v->next_v; delete temp; return; } node = node->next_v; } } void insertEdge(Node& graph, int v, int w) { Node* node_v = locate(graph, v); Node* node_w = locate(graph, w); if (node_v != 0 && node_w != 0) { Node* node = node_v; while (node->next_e != 0) { if (node->next_e->next_v->name == w) { return; } node = node->next_e; } node->next_e = new Node(0,0,0, node_w); } } void deleteEdge(Node& graph, int v, int w) { Node* node_v = locate(graph, v); Node* node_w = locate(graph, w); if (node_v != 0 && node_w != 0) { Node* node = node_v; while (node->next_e != 0) { if (node->next_e->next_v == node_w) { Node* temp = node->next_e; node->next_e = node->next_e->next_e; delete temp; } node = node->next_e; } } } void release(Node& graph) { Node* node = &graph; while (node->next_v != 0) { Node* n = node->next_v; while (n->next_e != 0) { Node* t = n->next_e; n->next_e = n->next_e->next_e; delete t; } Node* temp = node->next_v;; node->next_v = node->next_v->next_v; delete temp; } graph.next_v = 0; } void display(Node& graph) { Node* node = graph.next_v; while (node != 0) { cout << node->name << ": "; Node* n = node->next_e; while (n != 0) { cout << n->next_v->name << " "; n = n->next_e; } cout << endl; node = node->next_v; } } /*int size(Node& graph) { Node* node = graph.next_v; int count = 0; while (node != 0) { count++; node = node->next_v; } return count; } */ /*int getEdgeWeight(Node& graph, int v, int w) { Node* node_v = locate(graph, v); Node* node_w = locate(graph, w); if (node_v != 0 && node_w != 0) { Node* node = node_v->next_e; while (node != 0) { if (node->next_v == node_w) { return node->weight; } node = node->next_e; } } return 0; }*/ int main() { Node graph; insertVertex(graph, 5); insertVertex(graph, 4); insertVertex(graph, 3); insertVertex(graph, 2); insertVertex(graph, 1); insertEdge(graph, 1, 2); insertEdge(graph, 1, 3); insertEdge(graph, 4, 5); insertEdge(graph, 4, 1); insertEdge(graph, 4, 3); display(graph); deleteEdge(graph, 4, 1); deleteEdge(graph, 4, 1); cout << "-----------" << endl; display(graph); deleteVertex(graph, 4); cout << "-----------" << endl; display(graph); release(graph); return 0; }

2.一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点$v$出发的深度优先遍历的非递归过程。

为了方便，这里使用邻接矩阵

#include <iostream> #include <stack> #include <set> #include "graph.hpp" using namespace std; void DFS(Graph& graph, int v) { int pos = locate(graph, v); if (pos != -1) { stack<int> opened; set<int> closed; opened.push(pos); while (!opened.empty()) { int index = opened.top(); opened.pop(); if (closed.find(index) == closed.end()) { //！注意判断的位置 cout << graph.vertex[index] << " "; //添加子结点 for (int i = 0; i < graph.size; i++) { if (graph.weight[index][i] != 0) { opened.push(i); } } closed.insert(index); } } } } int main() { Graph graph; insertVetex(graph, 0); insertVetex(graph, 1); insertVetex(graph, 2); insertVetex(graph, 3); insertVetex(graph, 4); insertEdge(graph, 0, 1); insertEdge(graph, 0, 2); insertEdge(graph, 1, 0); insertEdge(graph, 1, 3); insertEdge(graph, 1, 4); insertEdge(graph, 2, 0); insertEdge(graph, 2, 3); insertEdge(graph, 3, 1); insertEdge(graph, 3, 2); insertEdge(graph, 3, 4); insertEdge(graph, 4, 1); insertEdge(graph, 4, 3); display(graph); cout << "search result: "; DFS(graph, 1); return 0; }

3.设计一个算法，求图$G$中距离顶点$v$的最短路径长度最大的一个顶点，设$v$可达其余各个顶点。

#include <iostream> #include "graph.hpp" #include <queue> #include <set> using namespace std; const int MAX_V = 100; /* Dijkstra本质是广度优先搜索。 */ int whichNodeCanLeadToMaxMinPath(Node& graph, int v) { if (locate(graph, v) == 0) return 0; int node_nums = size(graph); int min_length[MAX_V]; int pre_nodes[MAX_V]; //初始化(...) min_length[0] = 0; for (int i = 1; i <= node_nums; i++) { int length = getEdgeWeight(graph, v, i); min_length[i] = length == 0 ? INT32_MAX : length; pre_nodes[i] = v; } min_length[v] = 0; //算法开始 queue<int> q; set<int> closed; q.push(v); while (!q.empty()) { int index = q.front(); q.pop(); closed.insert(index); Node* node = locate(graph, index)->next_e; while (node != 0) { int node_name = node->next_v->name; //这一步可以覆盖到所有的edge int fresh_length = min_length[index] + getEdgeWeight(graph, index, node_name); if (min_length[node_name] > fresh_length) { pre_nodes[node_name] = index; min_length[node_name] = fresh_length; if (closed.find(node_name) != closed.end()) { closed.erase(node_name); } } if (closed.find(node_name) == closed.end()) { q.push(node_name); } node = node->next_e; } } //输出最大值 int max_path = 0; int max_vertext = 0; for (int i = 1; i <= node_nums; i++) { if (min_length[i] > max_path) { max_path = min_length[i]; max_vertext = i; } } return max_vertext; } int main() { Node graph; insertVertex(graph, 1); insertVertex(graph, 2); insertVertex(graph, 3); insertVertex(graph, 4); insertVertex(graph, 5); insertVertex(graph, 6); insertEdge(graph, 1, 2, 15); // 节点1->2的权重是2，下同 insertEdge(graph, 1, 3, 2); insertEdge(graph, 2, 4, 10); insertEdge(graph, 2, 5, 19); insertEdge(graph, 3, 2, 4); insertEdge(graph, 3, 5, 11); insertEdge(graph, 4, 6, 6); insertEdge(graph, 5, 6, 5); insertEdge(graph, 2, 1, 15); // 节点2->1的权重是2，下同 insertEdge(graph, 3, 1, 2); insertEdge(graph, 4, 2, 10); insertEdge(graph, 5, 2, 19); insertEdge(graph, 2, 3, 4); insertEdge(graph, 5, 3, 11); insertEdge(graph, 6, 4, 6); insertEdge(graph, 6, 5, 5); cout << whichNodeCanLeadToMaxMinPath(graph, 1) << endl; release(graph); return 0; }

4.试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的的有向图中是否存在由顶点$v_i$到$v_j$的路径$(v_i\ne v_j)$。

提示：深度优先搜索有递归形式，也有非递归形式。这里采用非递归形式。

#include <iostream> #include <stack> #include <set> #include "graph.hpp" using namespace std; bool doesHasAPath(Node& graph, int v, int w) { Node* node_v = locate(graph, v); Node* node_w = locate(graph, w); if (node_v != 0 && node_w != 0) { stack<Node*> s; set<Node*> closed; s.push(node_v); while (!s.empty()) { Node* node = s.top(); s.pop(); if (closed.find(node) == closed.end()) { closed.insert(node); Node* n = node->next_e; while (n != 0) { if (n->next_v == node_w) { return true; } s.push(n->next_v); n = n->next_e; } } } } return false; } int main() { Node graph; insertVertex(graph, 1); insertVertex(graph, 2); insertVertex(graph, 3); insertVertex(graph, 4); insertVertex(graph, 5); insertVertex(graph, 6); insertVertex(graph, 7); insertEdge(graph, 1, 2); insertEdge(graph, 1, 3); insertEdge(graph, 2, 4); insertEdge(graph, 2, 5); insertEdge(graph, 3, 2); insertEdge(graph, 3, 5); insertEdge(graph, 4, 6); insertEdge(graph, 5, 6); cout << "result(2, 7): " << doesHasAPath(graph, 2, 6) << endl; cout << "result(1, 7): " << doesHasAPath(graph, 1, 7) << endl; release(graph); return 0; }

同第三题图。 5.采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点(假定为$A和B$)之间是否存在一条长度为$k$的简章路径。

提示：如果是邻接矩阵，则可以使用矩阵幂的方法，但是这里是邻接表 提示：可以将此问题分解为 “是否存在长度为k-1的从顶点$a$到顶点$B$路径”的子问题 其中 $a$是结点$A$可以一步到达的结点。

#include <iostream> #include "graph.hpp" using namespace std; bool doesHasAPath(Node& graph, int v, int w, int k) { if (v == w && k == 0) { return true; } Node* node_v = locate(graph, v); //顶点A Node* node_w = locate(graph, w); //顶点B if (node_v != 0 && node_w != 0) { Node* n = node_v->next_e; while (n != 0) { if (doesHasAPath(graph, n->next_v->name, w, k - 1)) { return true; } n = n->next_e; } } return false; } int main() { Node graph; insertVertex(graph, 1); insertVertex(graph, 2); insertVertex(graph, 3); insertVertex(graph, 4); insertVertex(graph, 5); insertVertex(graph, 6); insertVertex(graph, 7); insertEdge(graph, 1, 2); insertEdge(graph, 1, 3); insertEdge(graph, 2, 4); insertEdge(graph, 2, 5); insertEdge(graph, 3, 2); insertEdge(graph, 3, 5); insertEdge(graph, 4, 6); insertEdge(graph, 5, 6); cout << "result: " << doesHasAPath(graph, 3, 5, 1) << endl; cout << "result: " << doesHasAPath(graph, 3, 5, 2) << endl; cout << "result: " << doesHasAPath(graph, 3, 5, 3) << endl; release(graph); return 0; }

同第三题图。