企业官网建设流程全解析

搜索无向图或有向图中两顶点间的所有最短路径应当使用DFS，配以适当的回溯操作即可实现路径搜索，具体代码如下，完全使用非递归方法实现

#include <iostream> #include <vector> #include <stdio.h> #include <malloc.h> #define N 5 //无环单边非负权重无向图顶点数 using namespace std; bool Enable(int start, int i, int j, bool p[][N], bool node[], int& edgeLinkRootUsed) //检查j是否是i的下一可达顶点, 是返回1否则返回0 { if (p[i][j] == false) return false; if (node[j]) return false; if (j == start && edgeLinkRootUsed == i) return false; return true; } int Search(int start, int k, int option, bool p[][N], bool node[], int& edgeLinkRootUsed) //在顶点k上搜索顶点option后的第一个可达顶点,搜索成功返回顶点标号，否则返回-1 { int m = option; for (m++; m < N; m++) { if (Enable(start, k, m, p, node, edgeLinkRootUsed)) return m; } return -1; } void FindRoad(bool isDiGraph, int start, int end, bool p[][N], int q[][N]) //路径搜索函数,寻找start和end间的所有路径 { int i, k; //i为当前顶点,k为下一可达顶点 int interval; int RoadLength; //路径长度 int count; //路径计数 bool node[N] = { 0 }; //Node数组标记各顶点在搜索过程中是否已被访问,Node[i]=0表示i+1顶点未被访问,Node[i]=1表示i+1顶点已被访问，这里首先初始化Node数组 int edgeLinkRootUsed = -1; vector<int> path_list; count = 0; //计数变量初始化 if (start != end) node[start] = 1; //start标记为已访问 i = start; k = -1; //i初始化为起始顶点 while (true) { if ((interval = Search(start, i, k, p, node, edgeLinkRootUsed)) == -1) //搜索从k起的下一个可达顶点失败 { if (i == start) //路径搜索完毕，退出 break; if (k != -1) { path_list.pop_back(); } } else { //搜索出下一可达顶点 if (k == -1) { path_list.push_back(i); //建立表示当前顶点i的路径节点 //下一可达顶点标记为已访问 } node[interval] = true; //下一可达顶点标记为已访问 if (i == start && isDiGraph == false) { edgeLinkRootUsed = interval; } i = interval; //更新i为下一可达顶点 if (i == end) //到达终点 { RoadLength = 0; count++; //路径计数变量自增 cout << "第" << count << "条路径" << endl; size_t run = 0; for (; run < path_list.size(); ++run) /*输出找到的路径*/ { cout << "V" << path_list[run] + 1 << "->"; if (run != 0) { RoadLength += q[path_list[run - 1]][path_list[run]]; } } cout << "V" << end + 1 << endl; cout << "路径长度" << RoadLength + q[path_list[run - 1]][end] << endl; //输出找到的路径长度 } else { k = -1; //k重置 continue; } } node[i] = false; k = i; //回溯 i = path_list.back(); } cout << "共有" << count << "条从V" << start + 1 << "到V" << end + 1 << "的路径" << endl; //输出找到的路径总数 } int main() { bool isDiGaph = false; int m, n; //m为起始顶点,n为终点 bool p[N][N] = { 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0 }; //初始化邻接矩阵p int q[N][N] = { 0, 3, 0, 7, 8, 3, 0, 4, 0, 9, 0, 4, 0, 9, 2, 7, 0, 9, 0, 9, 8, 9, 2, 9, 0 }; //初始化权重矩阵q,q[i][j]为连接i和j的边的权重 cout << "请输入要搜索的路径的起始顶点标号:" << endl; cin >> m; //输入起始顶点标号 cout << "请输入要搜索的路径的终点标号:" << endl; cin >> n; //输入终点标号 FindRoad(isDiGaph, m - 1, n - 1, p, q); //搜索m和n之间的所有路径并输出 return 0; }

对于如下的无向图：

其邻接矩阵和权重矩阵已在程序中数组的初始化列表中给出，程序运行时起始顶点输入为V1,终点输入为V3,则程序运行结果如下：

、

如果表示图的数据结构采用邻接链表则代码如下:

#include <iostream> #include <vector> #include <list> #include <tuple> #include <stdio.h> #include <malloc.h> using namespace std; struct edge { int weight; int end; edge(int w, int e) :weight(w), end(e) {} }; struct adjacency_list { void insert(int u, int v, int weight) { adj[u].push_back(edge(weight, v)); if (isDiGraph == false) adj[v].push_back(edge(weight, u)); } vector<list<edge>> adj; bool isDiGraph; adjacency_list(size_t v_num, bool id) :adj(v_num), isDiGraph(id) {} }; bool Enable(int start, int i, const list<edge>::const_iterator &j, bool node[], int& edgeLinkRootUsed) //检查j是否是i的下一可达顶点, 是返回1否则返回0 { if (node[j->end]) return false; if (j->end == start && edgeLinkRootUsed == i) return false; return true; } list<edge>::const_iterator Search(const adjacency_list& adj ,int start, int k, const list<edge>::const_iterator& option, bool node[], int& edgeLinkRootUsed) //在顶点k上搜索顶点option后的第一个可达顶点,搜索成功返回顶点标号，否则返回-1 { list<edge>::const_iterator m = option; if (option == adj.adj[k].end()) m = adj.adj[k].begin(); else ++m; for (; m != adj.adj[k].end(); ++m) { if (Enable(start, k, m, node, edgeLinkRootUsed)) return m; } return m; } #define N 5 //无环单边图顶点数 void FindRoad(const adjacency_list &adj, int start, int end) //路径搜索函数,寻找start和end间的所有路径 { int i; //i为当前顶点,k为下一可达顶点 list<edge>::const_iterator interval, k; int RoadLength; //路径长度 int count; //路径计数 bool node[N] = { 0 }; //Node数组标记各顶点在搜索过程中是否已被访问,Node[i]=0表示i+1顶点未被访问,Node[i]=1表示i+1顶点已被访问，这里首先初始化Node数组 int edgeLinkRootUsed = -1; vector<list<edge>::const_iterator> path_list; count = 0; //计数变量初始化 if (start != end) node[start] = 1; //start标记为已访问, i = start; k = adj.adj[start].cend(); //i初始化为起始顶点 while (true) { if ((interval = Search(adj, start, i, k, node, edgeLinkRootUsed)) == adj.adj[i].cend()) //搜索从k起的下一个可达顶点失败 { if (i == start) //路径搜索完毕，退出 break; if (k != adj.adj[i].cend()) { path_list.pop_back(); } } else { //搜索出下一可达顶点 if (k == adj.adj[i].cend()) { path_list.push_back(interval); //建立表示当前顶点i的路径节点 } else { path_list.back() = interval; } node[interval->end] = true; //下一可达顶点标记为已访问 if (i == start && adj.isDiGraph == false) { edgeLinkRootUsed = interval->end; } i = interval->end; //更新i为下一可达顶点 if (i == end) //到达终点 { RoadLength = 0; count++; //路径计数变量自增 cout << "第" << count << "条路径" << endl; size_t run = 0; cout << "V" << start + 1 << "->"; for (; run < path_list.size(); ++run) /*输出找到的路径*/ { cout << "V" << path_list[run]->end + 1; if (run < path_list.size() - 1) cout << "->"; RoadLength += path_list[run]->weight; } cout << "路径长度" << RoadLength << endl; //输出找到的路径长度 } else { k = adj.adj[i].cend(); //k重置 continue; } } node[i] = false; k = path_list.back(); //回溯 if (path_list.end() - 1 == path_list.begin()) { i = start; } else { i = (*(path_list.end() - 2))->end; } } cout << "共有" << count << "条从V" << start + 1 << "到V" << end + 1 << "的路径" << endl << endl; //输出找到的路径总数 } int main() { bool isDiGaph = false; int m, n; //m为起始顶点,n为终点 vector<tuple<int, int, int>> edge_info = { {0, 1, 3}, {0, 3, 7}, {0, 4, 8},{1, 4, 9}, {1, 2, 4}, {2, 4, 2}, {2, 3, 9}, {3, 4, 9} }; adjacency_list adj(N, isDiGaph); for (auto& run : edge_info) { adj.insert(get<0>(run), get<1>(run), get<2>(run)); } cout << "请输入要搜索的路径的起始顶点标号:" << endl; cin >> m; //输入起始顶点标号 cout << "请输入要搜索的路径的终点标号:" << endl; cin >> n; //输入终点标号 FindRoad(adj, m - 1, n - 1); //搜索m和n之间的所有路径并输出 return 0; }

如果要找出所有简单环，则只要稍作修改即可

#include <iostream> #include <vector> #include <list> #include <tuple> #include <stdio.h> #include <malloc.h> using namespace std; struct edge { int weight; int end; edge(int w, int e) :weight(w), end(e) {} }; struct adjacency_list { void insert(int u, int v, int weight) { adj[u].push_back(edge(weight, v)); if (isDiGraph == false) adj[v].push_back(edge(weight, u)); } vector<list<edge>> adj; bool isDiGraph; adjacency_list(size_t v_num, bool id) :adj(v_num), isDiGraph(id) {} }; bool Enable(int start, int i, const list<edge>::const_iterator& j, bool node[], int& edgeLinkRootUsed) //检查j是否是i的下一可达顶点, 是返回1否则返回0 { if (node[j->end]) return false; if (j->end == start && edgeLinkRootUsed == i) return false; return true; } list<edge>::const_iterator Search(const adjacency_list& adj, int start, int k, const list<edge>::const_iterator& option, bool node[], int& edgeLinkRootUsed) //在顶点k上搜索顶点option后的第一个可达顶点,搜索成功返回顶点标号，否则返回-1 { list<edge>::const_iterator m = option; if (option == adj.adj[k].end()) m = adj.adj[k].begin(); else ++m; for (; m != adj.adj[k].end(); ++m) { if (Enable(start, k, m, node, edgeLinkRootUsed)) return m; } return m; } #define N 5 //无环单边图顶点数 void FindRoad(const adjacency_list& adj, int start, int end, bool node[], int &count) //路径搜索函数,寻找start和end间的所有路径 { int i; //i为当前顶点,k为下一可达顶点 list<edge>::const_iterator interval, k; int RoadLength; //路径长度 int edgeLinkRootUsed = -1; vector<list<edge>::const_iterator> path_list; if (start != end) node[start] = 1; //start标记为已访问, i = start; k = adj.adj[start].cend(); //i初始化为起始顶点 while (true) { if ((interval = Search(adj, start, i, k, node, edgeLinkRootUsed)) == adj.adj[i].cend()) //搜索从k起的下一个可达顶点失败 { if (i == start) //路径搜索完毕，退出 break; if (k != adj.adj[i].cend()) { path_list.pop_back(); } } else { //搜索出下一可达顶点 if (k == adj.adj[i].cend()) { path_list.push_back(interval); //建立表示当前顶点i的路径节点 } else { path_list.back() = interval; } node[interval->end] = true; //下一可达顶点标记为已访问 if (i == start && adj.isDiGraph == false) { edgeLinkRootUsed = interval->end; } i = interval->end; //更新i为下一可达顶点 if (i == end) //到达终点 { RoadLength = 0; count++; //路径计数变量自增 cout << "第" << count << "条简单环" << endl; size_t run = 0; cout << "V" << start + 1 << "->"; for (; run < path_list.size(); ++run) /*输出找到的路径*/ { cout << "V" << path_list[run]->end + 1; if (run < path_list.size() - 1) cout << "->"; RoadLength += path_list[run]->weight; } cout << "简单环长度" << RoadLength << endl; //输出找到的路径长度 } else { k = adj.adj[i].cend(); //k重置 continue; } } node[i] = false; k = path_list.back(); //回溯 if (path_list.end() - 1 == path_list.begin()) { i = start; } else { i = (*(path_list.end() - 2))->end; } } } int main() { bool isDiGaph = false; int m, n; //m为起始顶点,n为终点 vector<tuple<int, int, int>> edge_info = { {0, 1, 3}, {0, 3, 7}, {0, 4, 8},{1, 4, 9}, {1, 2, 4}, {2, 4, 2}, {2, 3, 9}, {3, 4, 9} }; adjacency_list adj(N, isDiGaph); for (auto& run : edge_info) { adj.insert(get<0>(run), get<1>(run), get<2>(run)); } bool node[N] = { 0 }; int count = 0; for (int i = 0; i < N; ++i) { FindRoad(adj, i, i, node, count); node[i] = true; } cout << "共有" << count << "条简单环" << endl; return 0; }