搜索无向图或有向图中两顶点间的所有最短路径应当使用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表示i1顶点未被访问,Node[i]1表示i1顶点已被访问这里首先初始化Node数组 int edgeLinkRootUsed -1; vectorint 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)); } vectorlistedge adj; bool isDiGraph; adjacency_list(size_t v_num, bool id) :adj(v_num), isDiGraph(id) {} }; bool Enable(int start, int i, const listedge::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; } listedge::const_iterator Search(const adjacency_list adj ,int start, int k, const listedge::const_iterator option, bool node[], int edgeLinkRootUsed) //在顶点k上搜索顶点option后的第一个可达顶点,搜索成功返回顶点标号否则返回-1 { listedge::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为下一可达顶点 listedge::const_iterator interval, k; int RoadLength; //路径长度 int count; //路径计数 bool node[N] { 0 }; //Node数组标记各顶点在搜索过程中是否已被访问,Node[i]0表示i1顶点未被访问,Node[i]1表示i1顶点已被访问这里首先初始化Node数组 int edgeLinkRootUsed -1; vectorlistedge::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为终点 vectortupleint, 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(get0(run), get1(run), get2(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)); } vectorlistedge adj; bool isDiGraph; adjacency_list(size_t v_num, bool id) :adj(v_num), isDiGraph(id) {} }; bool Enable(int start, int i, const listedge::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; } listedge::const_iterator Search(const adjacency_list adj, int start, int k, const listedge::const_iterator option, bool node[], int edgeLinkRootUsed) //在顶点k上搜索顶点option后的第一个可达顶点,搜索成功返回顶点标号否则返回-1 { listedge::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为下一可达顶点 listedge::const_iterator interval, k; int RoadLength; //路径长度 int edgeLinkRootUsed -1; vectorlistedge::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为终点 vectortupleint, 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(get0(run), get1(run), get2(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; }