無向圖深度遍歷鄰接矩陣報(bào)告

.\無向圖的深度遍歷實(shí)驗(yàn)報(bào)告系別

計(jì)算機(jī)系

班級(jí)

學(xué)號(hào)

姓名課程名稱

數(shù)據(jù)結(jié)構(gòu)

實(shí)驗(yàn)日期實(shí)驗(yàn)名稱

圖的遍歷

成績實(shí)驗(yàn)?zāi)康模?.掌握?qǐng)D的結(jié)構(gòu)特征，以及鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)的特點(diǎn)和實(shí)現(xiàn)。2.掌握在精品文檔放心下載鄰接矩陣或鄰接表存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先和廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。感謝閱讀實(shí)驗(yàn)條件：計(jì)算機(jī)一臺(tái)，VisualC++6.0實(shí)驗(yàn)內(nèi)容：1.問題描述以鄰接矩陣或鄰接表為存儲(chǔ)結(jié)構(gòu)， 利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算精品文檔放心下載法遍歷一個(gè)無向圖。給出遍歷序列，若該圖不連通，給出其連通分量的個(gè)數(shù)和精品文檔放心下載各連通分量的遍歷序列。2.數(shù)據(jù)結(jié)構(gòu)類型定義采用鄰接矩陣為存儲(chǔ)結(jié)構(gòu)：typedefstructArcNode{intadj;}ArcNode;//鄰接矩陣元素的定義typedefstruct{VertexDatavertex[MAX_VERTEX_NUM];//為頂點(diǎn)的集合ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];感謝閱讀intvexnum,arcnum;//vexnum 為頂點(diǎn)數(shù)，arcnum為弧數(shù)謝謝閱讀}AdjMatrix;//鄰接矩陣的定義模塊劃分創(chuàng)建一個(gè)無向圖以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)：voidCreateUDN(AdjMatrix*G)謝謝閱讀鄰接矩陣的定位：intLocateVertex(AdjMatrix*G,VertexDatav)謝謝閱讀深度優(yōu)先遍歷：voidDepthFirstSearch(AdjMatrixG,intv)精品文檔放心下載無向圖的遍歷：voidTraverseGraph(AdjMatrixG)精品文檔放心下載主函數(shù)：voidmain().\詳細(xì)設(shè)計(jì)#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("輸入圖的頂點(diǎn)數(shù)和弧數(shù)：\n");謝謝閱讀scanf("%d,%d",&G->vexnum,&G->arcnum);精品文檔放心下載getchar();for(i=0;i<G->vexnum;i++){for(j=0;j<G->vexnum;j++)}printf("輸入圖的頂點(diǎn)：\n");for(i=0;i<G->vexnum;i++){scanf("%d",&G->vertex[i]);感謝閱讀47. }for(k=0;k<G->arcnum;k++){printf("輸入一條弧的兩個(gè)頂點(diǎn)：");精品文檔放心下載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.測(cè)試數(shù)據(jù)及結(jié)果第一組測(cè)試：輸入數(shù)據(jù)：頂點(diǎn)：1,2.\預(yù)測(cè)結(jié)果：輸出結(jié)點(diǎn)數(shù)據(jù)： 1,2輸出鄰接矩陣 0110實(shí)際結(jié)果：第二組測(cè)試：輸入數(shù)據(jù)：頂點(diǎn)：0,1,2,3,4預(yù)測(cè)結(jié)果：輸出結(jié)點(diǎn)數(shù)據(jù)： 0,1,2,3,4輸出鄰接矩陣 0111010010100111110100110實(shí)際結(jié)果：.\第三組測(cè)試：輸入數(shù)據(jù)：頂點(diǎn)：0,1,2,3,456預(yù)測(cè)結(jié)果：輸出結(jié)點(diǎn)數(shù)據(jù)： 0123456輸出鄰接矩陣 011110010100