无向图深度遍历邻接矩阵报告

. . 无向图的深度遍历实验报告无向图的深度遍历实验报告 系别计算机系班级学号 实验日期 成绩 课程名称 实验名称 实验目的 1.掌握图的结构特征， 以及邻接矩阵和邻接表存储结构的特点和实现。 2.掌握在邻 接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法思想及其程序实现。 实验条件 计算机一台， Visual C6.0 实验容 1. 问题描述 以邻接矩阵或邻接表为存储结构，利用深度优先搜索算法或广度优先搜索算 法遍历一个无向图。给出遍历序列，若该图不连通，给出其连通分量的个数和 各连通分量的遍历序列。 2. 数据结构类型定义 采用邻接矩阵为存储结构 typedef struct ArcNode { int adj; }ArcNode;// 邻接矩阵元素的定义 typedef struct { VertexData vertex[MAX_VERTEX_NUM];//为顶点的集合 ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum,arcnum;//vexnum为顶点数， arcnum 为弧数 }AdjMatrix; // 邻接矩阵的定义 3. 模块划分 1 创建一个无向图以邻接矩阵为存储结构void CreateUDNAdjMatrix *G . 学习.资料. 数据结构 图的遍历 . . 2 邻接矩阵的定位int LocateVertexAdjMatrix *G,VertexData v 3 深度优先遍历void DepthFirstSearchAdjMatrix G,int v 4 无向图的遍历void TraverseGraphAdjMatrix G 5 主函数 void main 4. 详细设计 5. include 6. include 7. include 8. define OK 1 9. define ERROR 0 10. define FALSE 0 11. define TRUE 1 12. define MAX_VERTEX_NUM 100 13. int visited[MAX_VERTEX_NUM]; 14. typedefint AdjType; 15. typedef int VertexData; 16. typedef enum{DG,DN,UDG,UDN}GraphKind; 17. typedefstruct ArcNode{ 18.AdjType adj; 19. } ArcNode; 20. typedef struct{ 21. 22. 23. VertexData vertex[MAX_VERTEX_NUM]; ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum,arcnum; 24. }AdjMatrix; 25. intLocateVertexAdjMatrix *G,VertexData v 26. { int jERROR,k; 27. fork0;kvexnum;k 28. ifG-vertex[k]v 29. {jk;break;} . 学习.资料. . . 30. return j; 31. } 32. 33. int GreateUDNAdjMatrix *G 34. {int i,j,k; 35.VertexData v1,v2; 36.printf“ 输入图的顶点数和弧数\n“; 37.scanf“d,d“, 38.getchar; 39.fori0;ivexnum;i 40.{ 41.forj0;jvexnum;j 42.G-arcs[i][j].adjFALSE; 43.} 44.printf“ 输入图的顶点 \n“; 45.fori0;ivexnum;i 46.{scanf“d“, 47.} 48.fork0;karcnum;k 49.{ 50.printf“ 输入一条弧的两个顶点“; 51.scanf“d,d“, 52. 53. 54. getchar; iLocateVertexG,v1; jLocateVertexG,v2; 55.G-arcs[i][j].adj1; 56.G-arcs[j][i].adj1; 57.} 58.returnOK; 59. } 60. . 学习.资料. . . 61. 62. void DepthFirstSearchAdjMatrix G,int v 63. {int j; 64. 65. 66. 67. 68. printf“d“,G.vertex[v]; printf“\n“; visited[v]TRUE; forj0;jG.vexnum;j ifvisited[j] 70. } 71. void TraverseGraphAdjMatrix G 72. {int i; 73. 74. 75. 76. } 77. 78. intmain 79. {int i,j; 80. AdjMatrix G; 81. GreateUDN 82. printf“ 此无向图的深度遍历为“; 83. TraverseGraphG; 84. printf“ 输出邻接矩阵 \n“; 85. fori0;iG.vexnum;i 86. 87. 88. 89. 90. 91. { forj0;jG.vexnum;j { printf“d “,G.arcs[i][j].adj; } fori0;iG.vexnum;i visited[i]FALSE; fori0;iG.vexnum;i ifvisited[i]DepthFirstSearchG,i; printf“\n“;} . 学习.资料. . . 92. return 0; 93. } 94. 95. 测试数据及结果 第一组测试 输入数据顶点 1,2 预测结果输出结点数据1,2 输出邻接矩阵0 1 1 0 实际结果 第二组测试 输入数据顶点 0,1,2,3,4 预测结果输出结点数据0,1,2,3,4 输出邻接矩阵0 1 1 1 0 . 学习.资料. . . 1 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 实际结果 第三组测试 输入数据顶点 0,1,2,3,4 5 6 预测结果输出结点数据0123456 输出邻接矩阵0 1 1 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 实际结果 . 学习.资料. . . . 学习.资料. . . 实验总结 开始出现各种问题，可能因为我不够理解图的遍历与