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

無向圖的深度遍歷實(shí)驗(yàn)報告系別計(jì)算機(jī)系班級學(xué)號姓名課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)日期實(shí)驗(yàn)名稱圖的遍歷成績實(shí)驗(yàn)?zāi)康模?.掌握圖的結(jié)構(gòu)特征，以及鄰接矩陣和鄰接表存儲結(jié)構(gòu)的特點(diǎn)和實(shí)現(xiàn)。2.掌握在鄰接矩陣或鄰接表存儲結(jié)構(gòu)下圖的深度優(yōu)先和廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。實(shí)驗(yàn)條件：計(jì)算機(jī)一臺，Visual C+6.0實(shí)驗(yàn)內(nèi)容：1. 問題描述以鄰接矩陣或鄰接表為存儲結(jié)構(gòu)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法遍歷一個無向圖。給出遍歷序列，若該圖不連通，給出其連通分量的個數(shù)和各連通分量的遍歷序列。2. 數(shù)據(jù)結(jié)構(gòu)類型定義采用鄰接矩陣為存儲結(jié)構(gòu)：typedef struct ArcNode int adj;ArcNode;/鄰接矩陣元素的定義typedef struct VertexData vertexMAX_VERTEX_NUM;/為頂點(diǎn)的集合 ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM; int vexnum,arcnum;/vexnum為頂點(diǎn)數(shù)，arcnum為弧數(shù)AdjMatrix; /鄰接矩陣的定義3. 模塊劃分(1) 創(chuàng)建一個無向圖以鄰接矩陣為存儲結(jié)構(gòu)：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) 主函數(shù)： void main()4. 詳細(xì)設(shè)計(jì)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(輸入圖的頂點(diǎn)數(shù)和弧數(shù)：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(輸入圖的頂點(diǎn)：n);45. for(i=0;ivexnum;i+)46. scanf(%d,&G-vertexi);47. 48. for(k=0;karcnum;k+)49. 50. printf(輸入一條弧的兩個頂點(diǎn)：);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. 測試數(shù)據(jù)及結(jié)果第一組測試： 輸入數(shù)據(jù)：頂點(diǎn)：1,2 預(yù)測結(jié)果：輸出結(jié)點(diǎn)數(shù)據(jù)：1,2 輸出鄰接矩陣 0 1 1 0實(shí)際結(jié)果：第二組測試： 輸入數(shù)據(jù)：頂點(diǎn)：0,1,2,3,4 預(yù)測結(jié)果：輸出結(jié)點(diǎn)數(shù)據(jù)：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 實(shí)際結(jié)果：第三組測試：輸入數(shù)據(jù)：頂點(diǎn)：0,1,2,3,4 5 6 預(yù)測結(jié)果：輸出結(jié)點(diǎn)數(shù)據(jù)：0123456輸出鄰接矩陣 0 1 1 1 1 0 0 1 0 1 0