.\無向圖的深度遍歷實驗報告系別

計算機系

班級

學號

姓名課程名稱

數據結構

實驗日期實驗名稱

圖的遍歷

成績實驗目的：1.掌握圖的結構特征，以及鄰接矩陣和鄰接表存儲結構的特點和實現。2.掌握在精品文檔放心下載鄰接矩陣或鄰接表存儲結構下圖的深度優先和廣度優先遍歷算法思想及其程序實現。感謝閱讀實驗條件：計算機一臺，VisualC++6.0實驗內容：1.問題描述以鄰接矩陣或鄰接表為存儲結構， 利用深度優先搜索算法或廣度優先搜索算精品文檔放心下載法遍歷一個無向圖。給出遍歷序列，若該圖不連通，給出其連通分量的個數和精品文檔放心下載各連通分量的遍歷序列。2.數據結構類型定義采用鄰接矩陣為存儲結構：typedefstructArcNode{intadj;}ArcNode;//鄰接矩陣元素的定義typedefstruct{VertexDatavertex[MAX_VERTEX_NUM];//為頂點的集合ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];感謝閱讀intvexnum,arcnum;//vexnum 為頂點數，arcnum為弧數謝謝閱讀}AdjMatrix;//鄰接矩陣的定義模塊劃分創建一個無向圖以鄰接矩陣為存儲結構：voidCreateUDN(AdjMatrix*G)謝謝閱讀鄰接矩陣的定位：intLocateVertex(AdjMatrix*G,VertexDatav)謝謝閱讀深度優先遍歷：voidDepthFirstSearch(AdjMatrixG,intv)精品文檔放心下載無向圖的遍歷：voidTraverseGraph(AdjMatrixG)精品文檔放心下載主函數：voidmain().\詳細設計#include<stdio.h>#include<stdlib.h>#include<math.h>#defineOK1#defineERROR0#defineFALSE0#defineTRUE1#defineMAX_VERTEX_NUM100精品文檔放心下載intvisited[MAX_VERTEX_NUM];感謝閱讀typedefintAdjType;typedefintVertexData;typedefenum{DG,DN,UDG,UDN}GraphKind;精品文檔放心下載typedefstructArcNode{AdjTypeadj;}ArcNode;typedefstruct{VertexDatavertex[MAX_VERTEX_NUM];謝謝閱讀ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];精品文檔放心下載intvexnum,arcnum;}AdjMatrix;intLocateVertex(AdjMatrix*G,VertexDatav)精品文檔放心下載{intj=ERROR,k;for(k=0;k<G->vexnum;k++)if(G->vertex[k]==v){j=k;break;}return(j);}32.intGreateUDN(AdjMatrix*G)謝謝閱讀{inti,j,k;.\VertexDatav1,v2;printf("輸入圖的頂點數和弧數：\n");謝謝閱讀scanf("%d,%d",&G->vexnum,&G->arcnum);精品文檔放心下載getchar();for(i=0;i<G->vexnum;i++){for(j=0;j<G->vexnum;j++)}printf("輸入圖的頂點：\n");for(i=0;i<G->vexnum;i++){scanf("%d",&G->vertex[i]);感謝閱讀47. }for(k=0;k<G->arcnum;k++){printf("輸入一條弧的兩個頂點：");精品文檔放心下載scanf("%d,%d",&v1,&v2);getchar();i=LocateVertex(G,v1);j=LocateVertex(G,v2);}return(OK);}60.61.voidDepthFirstSearch(AdjMatrixG,intv)謝謝閱讀{intj;64. printf("%d",G.vertex[v]);精品文檔放心下載printf("\n");.\visited[v]=TRUE;for(j=0;j<G.vexnum;j++)if(!visited[j]&&G.arcs[v][j].adj==1)感謝閱讀DepthFirstSearch(G,j);}voidTraverseGraph(AdjMatrixG)感謝閱讀72.{ inti;for(i=0;i<G.vexnum;i++)visited[i]=FALSE;感謝閱讀for(i=0;i<G.vexnum;i++)75. if(!visited[i]) DepthFirstSearch(G,i);謝謝閱讀}intmain(){inti,j;AdjMatrixG;GreateUDN(&G);printf("此無向圖的深度遍歷為：");TraverseGraph(G);printf("輸出鄰接矩陣\n");for(i=0;i<G.vexnum;i++){87.for(j=0;j<G.vexnum;j++)88.{89.printf("%d",G.arcs[i][j].adj);90.}91.printf("\n");}return0;}94.測試數據及結果第一組測試：輸入數據：頂點：1,2.\預測結果：輸出結點數據： 1,2輸出鄰接矩陣 0110實際結果：第二組測試：輸入數據：頂點：0,1,2,3,4預測結果：輸出結點數據： 0,1,2,3,4輸出鄰接矩陣 0111010010100111110100110實際結果：.\第三組測試：輸入數據：頂點：0,1,2,3,456預測結果：輸出結點數據： 0123456輸出鄰接矩陣 011110010100