DFS非递归实现搜索图中两顶点间的所有路径-北京尧图网络

搜索无向图或有向图中两顶点间的所有最短路径应当使用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; }

DFS非递归实现搜索图中两顶点间的所有路径

相关推荐

2025年质量管理手册编写指南：从过程方法到审核自查

一文读懂数据库事务

正弦激励下RL一阶电路响应与计算机辅助仿真分析

更多资讯

低压电工证报名后多久要考完试良心建议别被中介坑了

2026河南最新政策下建筑电工证号外省证如何转过来

潼南安监局电工证年审要多少钱？实操考试心里没底怕挂科怎么破？

潼南安监局电工证年审怎么搞？通过率揭秘来了！

建筑电工证号多少钱？怕考不过白交培训费？这几点你得知道

吴忠高压电工证培训机构怎么选？官方报名入口帮你避开实操考试坑

今日更新

电工证考试及格线你知道多少？值不值得考

南通电工证发证单位考前押题怎么搞？工地太忙根本没时间复习考试

黄陵县高低压电工证怎么考？上岗必备全流程避坑指南

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？