數(shù)據(jù)結(jié)構(gòu)實驗八、圖的建立和遍歷.doc

《數(shù)據(jù)結(jié)構(gòu)實驗八、圖的建立和遍歷.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、山東英才職業(yè)技工學(xué)校實驗報告系：__計算機(jī)_____成績_______________課程名稱__數(shù)據(jù)結(jié)構(gòu)___實驗項目名稱_______________________________專業(yè)班級__________________學(xué)生姓名___________________學(xué)號____________一、實驗?zāi)康?.理解圖的定義。2．熟練掌握圖的建立,深度優(yōu)先和廣度優(yōu)先遍歷算法的設(shè)計與實現(xiàn)。二、實驗原理定義圖的結(jié)構(gòu)體，建立并初始化一個圖，定義深度優(yōu)先和廣度優(yōu)先遍歷算法的函數(shù)，設(shè)計主函數(shù)實現(xiàn)圖的建立、深度優(yōu)先和廣度優(yōu)先遍歷過程。三、主要儀器設(shè)

2、備或材料1．計算機(jī)一臺2．Vc++編譯環(huán)境四、實驗方法與步驟include#includeusingnamespacestd;#defineMaxNum100typedefstringVertexType;typedefintEdgeType;structMGraph{VertexTypeV[MaxNum+1];EdgeTypeE[MaxNum+1][MaxNum+1];intVisited[MaxNum+1];intn,e;intflag;//1表示有向圖，0表示無向圖};typedefintDataTy

3、pe;#defineMAXQSIZE100typedefstruct{DataTypedata[MAXQSIZE];intfront,rear;}SqQueue;voidInitQueue(SqQueue&Q){Q.front=Q.rear=0;}intQueueEmpty(SqQueue&Q){if(Q.front==Q.rear)return1;elsereturn0;}intQueueFull(SqQueue&Q){if(Q.front==(Q.rear+1)%MAXQSIZE)return1;elsereturn0;}voidEnQu

4、eue(SqQueue&Q,DataTypee){if((Q.rear+1)%MAXQSIZE==Q.front)return;Q.data[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;}voidDeQueue(SqQueue&Q,DataType&e){if(Q.front==Q.rear)return;e=Q.data[Q.front];Q.front=(Q.front+1)%MAXQSIZE;}intFirstAdjVex(structMGraphG,intu){inti;for(i=1;i<=G.n;i+

5、+)if(G.E[u][i]==1)returni;return0;}intNextAdjVex(structMGraphG,intu,intw){inti;for(i=w+1;i<=G.n;i++)if(G.E[u][i]==1)returni;return0;}voidBFSTraverse(structMGraph&G,intStarti){inti;intu,w;//開始遍歷過程for(i=1;i<=G.n;i++)G.Visited[i]=0;//初始化訪問標(biāo)志SqQueueQ;InitQueue(Q);//初始化隊列cout<<"

6、廣度優(yōu)先遍歷序列如下:"<

7、nQueue(Q,w);//訪問的頂點w入隊列}w=NextAdjVex(G,u,w);}}}}voidmain(){structMGraphG1;inti,j,k;cout<<"請輸入頂點個數(shù):";cin>>G1.n;cout<<"請輸入邊數(shù)：";cin>>G1.e;cout<<"請輸入有向/無向標(biāo)志（1表有向，0表無向）";cin>>G1.flag;for(i=1;i<=G1.n;i++){cout<<"請輸入第"<>G1.V[i];}//初始化鄰接矩陣for(i=1;i<=G1.n;i++)for(j=1

8、;j<=G1.n;j++)G1.E[i][j]=0;//輸入邊的起點序號和終點序號以及邊的權(quán)值for(k=1;k<=G1.e;k++){cout<<"請輸入第"<<