《求图的简单路径和回路》由会员分享，可在线阅读，更多相关《求图的简单路径和回路（9页珍藏版）》请在金锄头文库上搜索。
1、求图的简单路径和回路 下面是用邻接表存储无向图，然后输出图中指定顶点间的指定长度的简单路径，简单路径 就是路径中的顶点不重复，还有一个就是求出图中经过某顶点的回路，都是对图的遍历算 法的应用，主要是深度优先的遍历，加上简单的回溯。下面是代码1./文件“graph.h“ 2. 3.#include 4.#include 5.#include 6.using namespace std; 7. 8.bool visited20; 9.int path20; 10. 11.struct ArcNode 12. 13. int adjvex; 14. ArcNode *nextarc; 15.; 16
2、. 17.struct VexNode 18. 19. string data; 20. ArcNode *firstarc; 21.; 22. 23.class NDGraph 24. 25.private: 26. VexNode vertices20; 27. int vexnum; 28. int arcnum; 29.public: 30. NDGraph() 31. 32. vexnum=0; 33. arcnum=0; 34. 35. 36. int GetVexNum() 37. 38. return vexnum; 39. 40. 41. int Locate_Vex(str
3、ing v) 42. 43. for(int i=0;ivexnumarcnum; 56. while(vexnum20) 57. 58. coutvexnumarcnum; 60. 61. 62. coutverticesi.data; 66. verticesi.firstarc=NULL; 67. 68. 69. for(k=0;kv1v2; 73. 74. i=Locate_Vex(v1); 75. j=Locate_Vex(v2); 76. 77. while(i = -1 | j = -1) 78. 79. coutv1v2; 81. i=Locate_Vex(v1); 82. j
4、=Locate_Vex(v2); 83. 84. 85. ArcNode *p=new ArcNode; 86. p-adjvex=j; 87. p-nextarc=verticesi.firstarc; 88. verticesi.firstarc=p; 89. 90. /置对称边 91. ArcNode *q=new ArcNode; 92. q-adjvex=i; 93. q-nextarc=verticesj.firstarc; 94. verticesj.firstarc=q; 95. 96. coutnextarc) 115. 116. w=p-adjvex; 117. if(!v
5、isitedw) 118. DFS(w); 119. 120. 121. 122. void BFS_Traverse() 123. 124. for(int i=0;i qu; 136. int w,k; 137. ArcNode *p=NULL; 138. qu.push(v); 139. while(!qu.empty() 140. 141. w=qu.front(); 142. qu.pop(); 143. for(p=verticesw.firstarc;p;p=p-nextarc) 144. 145. k=p-adjvex; 146. if(!visitedk) 147. 148.
6、 visitedk=true; 149. cout“; 168. coutadjvex; 181. if(!visitedm) 182. Print_X_Y_Path(m,v,l,d); 183. p=p-nextarc; 184. 185. 186. /恢复环境，使顶点可重新使用 187. /路径长度减一 188.loop: visitedu=false; 189. d-; 190. 191. 192. void Print_X_X_Path(int i,int j,int d) 193. 194. /找出从 i 到 i 的回路,思想和上面的类似 195. int v,k; 196. Arc
7、Node *p; 197. visitedi=true; 198. d+; 199. pathd=i; 200. if(i = j k“; 204. coutadjvex; 214. if(!visitedv | v = j) 215. Print_X_X_Path(v,j,d); 216. p=p-nextarc; 217. 218. 219. 220.lop: visitedi=false; 221. d-; 222. 223. 224.; 主函数文件1.#include “graph.h“ 2.#include 3.#include 4.using namespace std; 5. 6
8、.int main() 7. 8. NDGraph G; 9. string v1,v2; 10. int u,v; 11. int num; 12. G.Create_NDGraph(); 13. 14. coutv1v2num; 25. 26. u=G.Locate_Vex(v1); 27. v=G.Locate_Vex(v2); 28. if(u = -1 | v = -1) 29. 30. coutv1; 42. u=G.Locate_Vex(v1); 43. if(u = -1) 44. 45. coutv4v5v3 16.v1v4v2v3 17.输入一个顶点名称，将输出所有经过它的回路：v4 18.经过顶点 v4 的所有回路如下： 19.v4v5v3v2v4 20.v4v5v3v2v1v4 21.v4v2v3v5v4 22.v4v2v1v4 23.v4v1v2v3v5v4 24.v4v1v2v4 25.Press any key to continue 下面是生成的无向图示例：为了更好得理解回溯的过程，可以画画像下面这样的示意图，比如我求 V1 到 V3 的长度为 3 的路径的过程图可能和你画的不一样，但是主要就是理清一下思路，不会在一重重的递归中乱掉
