無向圖深度遍歷鄰接矩陣報告.doc

無向圖的深度遍歷實驗報告系別計算機系班級學號姓名課程名稱數據結構實驗日期實驗名稱圖的遍歷成績實驗目的：1.掌握圖的結構特征，以及鄰接矩陣和鄰接表存儲結構的特點和實現。2.掌握在鄰接矩陣或鄰接表存儲結構下圖的深度優(yōu)先和廣度優(yōu)先遍歷算法思想及其程序實現。實驗條件：計算機一臺，Visual C+6.0實驗內容：1. 問題描述以鄰接矩陣或鄰接表為存儲結構，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法遍歷一個無向圖。給出遍歷序列，若該圖不連通，給出其連通分量的個數和各連通分量的遍歷序列。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) 創(chuàng)建一個無向圖以鄰接矩陣為存儲結構：void CreateUDN(AdjMatrix *G)(2) 鄰接矩陣的定位：int LocateVertex(AdjMatrix *G,VertexData v)(3) 深度優(yōu)先遍歷：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