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

无向图的深度遍历实验报告系别计算机系班级学号姓名课程名称数据结构实验日期实验名称图的遍历成绩实验目的：1.掌握图的结构特征，以及邻接矩阵和邻接表存储结构的特点和实现。2.掌握在邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法思想及其程序实现。实验条件：计算机一台，Visual C+6.0实验内容：1. 问题描述以邻接矩阵或邻接表为存储结构，利用深度优先搜索算法或广度优先搜索算法遍历一个无向图。给出遍历序列，若该图不连通，给出其连通分量的个数和各连通分量的遍历序列。2. 数据结构类型定义采用邻接矩阵为存储结构：typedef struct ArcNode int adj;ArcNode;/邻接矩阵元素的定义typedef struct VertexData vertexMAX_VERTEX_NUM;/为顶点的集合 ArcNode arcsMAX_VERTEX_NUMMAX_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. #include8. #define OK 19. #define ERROR 010. #define FALSE 011. #define TRUE 112. #define MAX_VERTEX_NUM 10013. int visitedMAX_VERTEX_NUM;14. typedef int AdjType;15. typedef int VertexData;16. typedef enumDG,DN,UDG,UDNGraphKind;17. typedef struct ArcNode18. AdjType adj;19. ArcNode;20. typedef struct21. VertexData vertexMAX_VERTEX_NUM;22. ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;23. int vexnum,arcnum;24. AdjMatrix;25. int LocateVertex(AdjMatrix *G,VertexData v)26. int j=ERROR,k;27. for(k=0;kvexnum;k+)28. if(G-vertexk=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,&G-vexnum,&G-arcnum);38. getchar();39. for(i=0;ivexnum;i+)40. 41. for(j=0;jvexnum;j+)42. G-arcsij.adj=FALSE;43. 44. printf(输入图的顶点：n);45. for(i=0;ivexnum;i+)46. scanf(%d,&G-vertexi);47. 48. for(k=0;karcnum;k+)49. 50. printf(输入一条弧的两个顶点：);51. scanf(%d,%d,&v1,&v2);52. getchar();53. i=LocateVertex(G,v1);54. j=LocateVertex(G,v2);55. G-arcsij.adj=1;56. G-arcsji.adj=1;57. 58. return(OK);59. 60.61.62. void DepthFirstSearch(AdjMatrix G,int v)63. int j;64. printf(%d,G.vertexv);65. printf(n);66. visitedv=TRUE;67. for(j=0;jG.vexnum;j+)68. if(!visitedj&G.arcsvj.adj=1)69. DepthFirstSearch(G,j);70. 71. void TraverseGraph(AdjMatrix G)72. int i;73. for(i=0;iG.vexnum;i+) visitedi=FALSE;74. for(i=0;iG.vexnum;i+)75. if(!visitedi) DepthFirstSearch(G,i);76. 77.78. int main()79. int i,j;80. AdjMatrix G;81. GreateUDN(&G);82. printf(此无向图的深度遍历为：);83. TraverseGraph(G);84. printf(输出邻接矩阵n);85. for(i=0;iG.vexnum;i+)86. 87. for(j=0;jG.vexnum;j+)88. 89. printf(%d ,G.arcsij.adj);90. 91. 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