實驗四圖的深度優(yōu)先與廣度優(yōu)先遍歷

實驗報告學(xué)院（系）名稱：計算機與通訊工程學(xué)院姓名**學(xué)號********專業(yè)計算機科學(xué)與技術(shù)班級2015級*班實驗項目實驗四：圖的深度優(yōu)先與廣度優(yōu)先遍歷課程名稱數(shù)據(jù)結(jié)構(gòu)與算法課程代碼0661013實驗時間2017年5月12日第5-6節(jié)實驗地址7-216查核特點考勤違標(biāo)準(zhǔn)實驗過程程序運轉(zhuǎn)回答以下問題實驗報告紀(jì)狀況成績功能25分20分15分30分5分5分成績欄其余批閱建議:○完好評論在實驗□功能完美,○正確講堂中的表○較完好○基本正確□功能不全○有○有查核現(xiàn)，包含實○一般內(nèi)容驗態(tài)度、編□有小錯○有提示○無○無教師署名：寫程序過程○內(nèi)容很少○沒法回答□沒法運轉(zhuǎn)等內(nèi)容等。○無報告一、實驗?zāi)康睦斫鈭D的邏輯特點；掌握理解圖的兩種主要儲存結(jié)構(gòu)（毗鄰矩陣和毗鄰表），掌握圖的結(jié)構(gòu)、深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法二、實驗題目與要求1.每位同學(xué)按下述要務(wù)實現(xiàn)相應(yīng)算法：依據(jù)從鍵盤輸入的數(shù)據(jù)創(chuàng)立圖（圖的儲存結(jié)構(gòu)可采納毗鄰矩陣或毗鄰表），并對圖進行深度優(yōu)先搜尋和廣度優(yōu)先搜尋1）問題描繪：在主程序中供給以下菜單：1圖的成立2深度優(yōu)先遍歷圖3廣度優(yōu)先遍歷圖0結(jié)束2）實驗要求：圖的儲存可采納毗鄰表或毗鄰矩陣；定義以下過程：CreateGraph( ):按從鍵盤的數(shù)據(jù)成立圖DFSGrahp( )：深度優(yōu)先遍歷圖BFSGrahp( )：廣度優(yōu)先遍歷圖3）實驗提示:圖的儲存可采納毗鄰表或毗鄰矩陣；圖儲存數(shù)據(jù)種類定義（毗鄰表儲存）defineMAX_VERTEX_NUM8拓?fù)渑判颍航o出一個圖的結(jié)構(gòu)，輸出其拓?fù)渑判蛐蛄校O點序列用空格分開），要求在同樣條件下，編號小的極點在前。3．利用最小生成樹算法解決通訊網(wǎng)的總造價最低問題1）問題描繪：若在n個城市之間建通訊網(wǎng)絡(luò)，架設(shè)n-1條線路即可。怎樣以最低的經(jīng)濟代價建設(shè)這個通訊網(wǎng)，是一個網(wǎng)絡(luò)的最小生成樹問題。2）實驗要求：利用Prim算法求網(wǎng)的最小生成樹。實現(xiàn)提示：通訊線路一旦成立，必定是雙向的。所以，結(jié)構(gòu)最小生成樹的網(wǎng)必定是無向網(wǎng)。為簡單起見，圖的極點數(shù)不超出10個，網(wǎng)中邊的權(quán)值設(shè)置成小于100。三、實驗過程與實驗結(jié)果應(yīng)包含以下主要內(nèi)容：數(shù)據(jù)結(jié)構(gòu)定義圖是由定點會合及定點間的關(guān)系會合構(gòu)成的一種數(shù)據(jù)結(jié)構(gòu)，其形式化定義為Graph=（V，E）此中，V={x|x∈某個數(shù)據(jù)對象}是定點的有限非空會合；E={（x,y）|x,y∈V∧Path(x,y)}是極點之間關(guān)系的有限會合，叫做便集。會合E中的Path（x,y）表示極點x和極點y之間有一條直接連線，即（x,y）表示一條邊，它是有方向的。算法設(shè)計思路簡介算法描繪：能夠用自然語言、偽代碼或流程圖等方式1、圖的深度優(yōu)先搜尋：在接見圖中某一同始點V后，由V出發(fā)，接見它的任一毗鄰極點w1;再從w1；出發(fā)，接見與w1毗鄰但還沒有接見過得極點w2；而后再從w2出發(fā)，進行近似的接見，,這樣進行下去，直至抵達全部的毗鄰極點都被接見過的極點u為止；接著退回一步，回溯到u的前一個毗鄰極點，看它能否還有其余沒有被接見過的毗鄰點。假如有，則接見此毗鄰點，以后再此后頂點出發(fā)，進行與前述近似的接見；假如沒有，就再退回一步進行搜尋。重復(fù)上述過程，直至圖中全部和V連通的極點都被接見到。若此時圖中另有極點未被接見，則說明該圖不是連通圖，另選圖中一個不曾被接見的極點作開端點，重復(fù)上述過程，直至圖中全部極點都被接見過為止。圖的廣度優(yōu)先搜尋：使用廣度優(yōu)先搜尋（BFS）在接見了開端極點V以后，由V出發(fā)，挨次接見V的各個不曾被接見過的毗鄰點w1,w2,,wt,而后再次序接見w1,w2,,wt，的全部還為接見過的毗鄰點。再從這些極點出發(fā)，接見它們還未接見過的毗鄰點，，這樣做下去，直到圖中全部極點都被接見過為止。2、1）將沒有前驅(qū)（入度為零）的極點進棧。2）從棧中退出棧頂元素輸出，并把該極點引出的全部弧刪去，即把它的各個毗鄰點的入度減1，同時將目前已輸出的極點個數(shù)加1.3）將新的入度為零的極點再進棧。4）重復(fù)（2）、（2）兩步，直到棧為空為止。此時或許已經(jīng)輸出前部極點，或許剩下的極點中沒有入度為零的極點。3、設(shè)置一個n*n的矩陣A（k），此中除對角線元素為0外，其余元素A(k)[i][j]表示極點i到極點j的路徑長度，k表示運算步驟。開始時k=-1,A(-1)[i][j]=arcs[i][j],即A為圖的毗鄰矩陣。此后逐漸試試在原路徑中加入其余極點作為中間點，假如增添中間點極點后，獲得的路徑比本來的路徑短，

則以此新路徑取代本來路徑，

改正矩陣元素。詳細(xì)做法為：第0步讓全部路徑上加入中間點

0，去

A[i][j]

與

A[i][0]+A[o][j]

中較小的值作

A[i][j]的新值，達成后獲得

A(0)這樣進行下去，當(dāng)?shù)?/p>

n-1

步達成后，獲得

A(n-1),A(n-1)

即為所求的結(jié)果，

A(n-1)[i][j]

表示從

i到

j

路徑上的中間極點的序號小于或等于

n-1

的最短路徑的長度，即

A(n-1)[i][j]

表示從

i到j(luò)

的最短路徑的長度。算法的實現(xiàn)和測試結(jié)果：包含算法運轉(zhuǎn)時的輸入、輸出，實驗中出現(xiàn)的問題及解決方法等1、2、3、算法時間復(fù)雜度剖析1、深度優(yōu)先遍歷：O（n*n）.廣度優(yōu)先遍歷：O（n*n）.2、O（n+e）.3、O(n*n*n).四、收獲與領(lǐng)會不想說什么，這章的程序太難了，每次一想起來數(shù)據(jù)結(jié)構(gòu)還沒做就煩，前兩個題基本上一天能做一道題，第三題也就是騙騙OJ，實質(zhì)上還有個小BUG，等有空再寫個真實切合題意的程序吧。五、源代碼清單1、#include<iostream>usingnamespacestd;#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20dj=0;for(intk=0;k<m;k++){cin>>i>>j;[i-1][j-1].adj=[j-1][i-1].adj=1;}}boolvisited[MAX_VERTEX_NUM];intcount=0;voidDFS(GraphG,int{

v)visited[v-1]=count++;cout<<v;if(count<cout<<"";

true;for(inti=v;i<;i++)if[v-1][i].adj!=0&&!visited[i])DFS(G,[i]);}voidDFSTraverse(GraphG){intv=0;for(v=0;v<;v++){visited[v]=

false

;}v=1;dj!=0&&!visited[i]){EnQueue(queue,[i]);visited[i]=true;}}}intmain( ){GraphG1;intm=0;ata=i+1;[i].firstarc=NULL;}for(intk=0;k<e;k++){cin>>i>>j;ArcNode*s,*p;s=(ArcNode*)malloc(sizeof(ArcNode));s->adjvex=j-1;s->nextarc=NULL;if[i-1].firstarc==NULL){[i-1].firstarc=s;}else{p=[i-1].firstarc;while(p->nextarc!=NULL){p=p->nextarc;}p->nextarc=s;}}}voidFindInDegree(GraphG,intindegree[]){inti;ArcNode*p;for(i=0;i<;i++)indegree[i]=0;for(i=0;i<;i++){p=[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}voidTopologicalSort(GraphG){inti,k,count,indegree[MAX_VERTEX_NUM];boolvisited[MAX_VERTEX_NUM];for(i=0;i<;i++)visited[i]=ArcNode*p;

false;count=0;FindInDegree(G,indegree);while(count<{for(i=0;i<;i++){if(indegree[i]==0&&visited[i]=={

false)cout<<[i].data;if(count<cout<<"";count++;visited[i]=true;for(p=[i].firstarc;p;p=p->nextarc){k=p->adjvex;indegree[k]--;}break;}}}}intmain( ){intn;dj=INFINITY;}for(intk=0;k<m;k++){cin>>i>>j>>w;if[i-1][j-1].adj>w)[i-1][j-1].adj=[j-1][i-1].adj=w;}}voidFloyd(GraphG,intn,intm){inti,j;intmax=0;intA[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intpath[MAX_VERTEX_NUM][MAX_VERTEX_NUM];for(i=0;i<n;i++)for(j=0;j<n;j++){A[i][j]=[i][j].adj;if(A[i][j]<INFINITY)path[i][j]=i;elsepath[i][j]=0;}intt;intsum;for(i=0;i<n;i++){t=0;sum=0;for(j=0;j<n;j++)if(A[i][j]<1000){t++;sum=sum+A[i][j];if(t>=n-1&&sum<20){cout<<sum;exit(0);}elsecontinue;}}for(intk=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)if(A[i][k]+A[k][j]<A[i][j]){A[i][j]=A[i][k]+A[k][j];path[i][j]=path[k][j];}dj!=0&&!visited[i])DFS(G,[i]);}voidDFSTraverse(GraphG){intv=0;for(v=