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

. . 无向图的深度遍历实验报告无向图的深度遍历实验报告系别计算机系班级学号实验日期成绩课程名称实验名称实验目的： 1.掌握图的结构特征，以及邻接矩阵和邻接表存储结构的特点和实现。 2.掌握在邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法思想及其程序实现。实验条件：计算机一台， Visual C++6.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 CreateUDN(AdjMatrix *G) . 学习.资料. 数据结构图的遍历 . . (2) 邻接矩阵的定位：int LocateVertex(AdjMatrix *G,VertexData v) (3) 深度优先遍历：void DepthFirstSearch(AdjMatrix G,int v) (4) 无向图的遍历：void TraverseGraph(AdjMatrix 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. intLocateVertex(AdjMatrix *G,VertexData v) 26. { int j=ERROR,k; 27. for(k=0;kvexnum;k++) 28. if(G-vertex[k]==v) 29. {j=k;break;} . 学习.资料. . . 30. return (j); 31. } 32. 33. int GreateUDN(AdjMatrix *G) 34. {int i,j,k; 35.VertexData v1,v2; 36.printf(“ 输入图的顶点数和弧数：\n“); 37.scanf(“%d,%d“, 38.getchar(); 39.for(i=0;ivexnum;i++) 40.{ 41.for(j=0;jvexnum;j++) 42.G-arcs[i][j].adj=FALSE; 43.} 44.printf(“ 输入图的顶点： \n“); 45.for(i=0;ivexnum;i++) 46.{scanf(“%d“, 47.} 48.for(k=0;karcnum;k++) 49.{ 50.printf(“ 输入一条弧的两个顶点：“); 51.scanf(“%d,%d“, 52. 53. 54. getchar(); i=LocateVertex(G,v1); j=LocateVertex(G,v2); 55.G-arcs[i][j].adj=1; 56.G-arcs[j][i].adj=1; 57.} 58.return(OK); 59. } 60. . 学习.资料. . . 61. 62. void DepthFirstSearch(AdjMatrix G,int v) 63. {int j; 64. 65. 66. 67. 68. printf(“%d“,G.vertex[v]); printf(“\n“); visited[v]=TRUE; for(j=0;jG.vexnum;j++) if(!visited[j] 70. } 71. void TraverseGraph(AdjMatrix G) 72. {int i; 73. 74. 75. 76. } 77. 78. intmain() 79. {int i,j; 80. AdjMatrix G; 81. GreateUDN( 82. printf(“ 此无向图的深度遍历为：“); 83. TraverseGraph(G); 84. printf(“ 输出邻接矩阵 \n“); 85. for(i=0;iG.vexnum;i++) 86. 87. 88. 89. 90. 91. { for(j=0;jG.vexnum;j++) { printf(“%d “,G.arcs[i][j].adj); } for(i=0;iG.vexnum;i++) visited[i]=FALSE; for(i=0;iG.vexnum;i++) if(!visited[i])DepthFirstSearch(G,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 实际结果： . 学习.资料. . . . 学习.资料. . . 实验总结：开始出现各种问题，可能因为我不够理解图的遍历与