實(shí)驗(yàn)四：圖的深度優(yōu)先及廣度優(yōu)先遍歷

1、-. z.實(shí)驗(yàn)報(bào)告學(xué)院系名稱：計(jì)算機(jī)與通信工程學(xué)院* * *專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)2015級(jí)*班實(shí)驗(yàn)工程實(shí)驗(yàn)四：圖的深度優(yōu)先與廣度優(yōu)先遍歷課程名稱數(shù)據(jù)構(gòu)造與算法課程代碼0661013實(shí)驗(yàn)時(shí)間2017年5 月 12日第5-6節(jié)實(shí)驗(yàn)地點(diǎn)7-216考核標(biāo)準(zhǔn)實(shí)驗(yàn)過(guò)程25分程序運(yùn)行20分答復(fù)以下問(wèn)題15分實(shí)驗(yàn)報(bào)告30分特色功能5分考勤違紀(jì)情況5分成績(jī)成績(jī)欄其它批改意見:教師簽字：考核內(nèi)容評(píng)價(jià)在實(shí)驗(yàn)課堂中的表現(xiàn)，包括實(shí)驗(yàn)態(tài)度、編寫程序過(guò)程等內(nèi)容等。功能完善, 功能不全有小錯(cuò)無(wú)法運(yùn)行正確根本正確有提示無(wú)法答復(fù)完整較完整一般內(nèi)容極少無(wú)報(bào)告有無(wú)有無(wú)實(shí)驗(yàn)?zāi)康睦斫鈭D的邏輯特點(diǎn)；掌握理解圖的兩種主要存儲(chǔ)構(gòu)造鄰接矩陣

2、和鄰接表，掌握?qǐng)D的構(gòu)造、深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法實(shí)驗(yàn)題目與要求1. 每位同學(xué)按下述要*現(xiàn)相應(yīng)算法：根據(jù)從鍵盤輸入的數(shù)據(jù)創(chuàng)立圖圖的存儲(chǔ)構(gòu)造可采用鄰接矩陣或鄰接表，并對(duì)圖進(jìn)展深度優(yōu)先搜索和廣度優(yōu)先搜索1問(wèn)題描述：在主程序中提供以下菜單：1圖的建立2深度優(yōu)先遍歷圖3廣度優(yōu)先遍歷圖0完畢2實(shí)驗(yàn)要求：圖的存儲(chǔ)可采用鄰接表或鄰接矩陣；定義以下過(guò)程：CreateGraph(): 按從鍵盤的數(shù)據(jù)建立圖DFSGrahp()：深度優(yōu)先遍歷圖 BFSGrahp()：廣度優(yōu)先遍歷圖3實(shí)驗(yàn)提示: 圖的存儲(chǔ)可采用鄰接表或鄰接矩陣； 圖存儲(chǔ)數(shù)據(jù)類型定義鄰接表存儲(chǔ) # define MA*_VERTE*_NUM 8 /

3、頂點(diǎn)最大個(gè)數(shù)typedef struct Arode int adjve*; struct Arode *ne*tarc; int weight; /邊的權(quán)Arode; /表結(jié)點(diǎn)# define Verte*Type int /頂點(diǎn)元素類型typedef struct VNode int degree,indegree; /頂點(diǎn)的度，入度 Verte*Type data; Arode *firstarc; Vnode /*頭結(jié)點(diǎn)*/; typedef struct Vnode verticesMA*_VERTE*_NUM; int ve*num,arum;/頂點(diǎn)的實(shí)際數(shù)，邊的實(shí)際數(shù)ALGrap

4、h; 4注意問(wèn)題: 注意理解各算法實(shí)現(xiàn)時(shí)所采用的存儲(chǔ)構(gòu)造。 注意區(qū)別正、逆鄰接。2. 拓?fù)渑判颍航o出一個(gè)圖的構(gòu)造，輸出其拓?fù)渑判蛐蛄许旤c(diǎn)序列用空格隔開，要求在同等條件下，編號(hào)小的頂點(diǎn)在前。3利用最小生成樹算法解決通信網(wǎng)的總造價(jià)最低問(wèn)題1問(wèn)題描述：假設(shè)在 n 個(gè)城市之間建通信網(wǎng)絡(luò)，架設(shè) n-1 條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建立這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)絡(luò)的最小生成樹問(wèn)題。2實(shí)驗(yàn)要求：利用 Prim 算法求網(wǎng)的最小生成樹。3) 實(shí)現(xiàn)提示：通信線路一旦建立，必然是雙向的。因此，構(gòu)造最小生成樹的網(wǎng)一定是無(wú)向網(wǎng)。為簡(jiǎn)單起見，圖的頂點(diǎn)數(shù)不超過(guò) 10 個(gè)，網(wǎng)中邊的權(quán)值設(shè)置成小于 100。實(shí)驗(yàn)過(guò)程與實(shí)驗(yàn)結(jié)果應(yīng)包

5、括如下主要內(nèi)容：數(shù)據(jù)構(gòu)造定義圖是由定點(diǎn)集合及定點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)構(gòu)造，其形式化定義為Graph = V，E其中，V = *|*個(gè)數(shù)據(jù)對(duì)象是定點(diǎn)的有限非空集合；E = *,y|*,yVPath(*,y)是頂點(diǎn)之間關(guān)系的有限集合，叫做便集。集合E中的Path*,y表示頂點(diǎn)*和頂點(diǎn)y之間有一條直接連線，即*,y表示一條邊，它是有方向的。算法設(shè)計(jì)思路簡(jiǎn)介算法描述：可以用自然語(yǔ)言、偽代碼或流程圖等方式1、圖的深度優(yōu)先搜索：在訪問(wèn)圖中*一起始點(diǎn)V后，由V出發(fā)，訪問(wèn)它的任一鄰接頂點(diǎn)w1;再?gòu)膚1；出發(fā)，訪問(wèn)與w1鄰接但還沒(méi)有訪問(wèn)過(guò)得頂點(diǎn)w2；然后再?gòu)膚2出發(fā)，進(jìn)展類似的訪問(wèn)，,如此進(jìn)展下去，直至到

6、達(dá)所有的鄰接頂點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn)u為止；接著退回一步，回溯到u的前一個(gè)鄰接頂點(diǎn)，看它是否還有其他沒(méi)有被訪問(wèn)過(guò)的鄰接點(diǎn)。如果有，則訪問(wèn)此鄰接點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)展與前述類似的訪問(wèn)；如果沒(méi)有，就再退回一步進(jìn)展搜索。重復(fù)上述過(guò)程，直至圖中所有和V連通的頂點(diǎn)都被訪問(wèn)到。假設(shè)此時(shí)圖*有頂點(diǎn)未被訪問(wèn)，則說(shuō)明該圖不是連通圖，另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。圖的廣度優(yōu)先搜索：使用廣度優(yōu)先搜索BFS在訪問(wèn)了起始頂點(diǎn)V之后，由V出發(fā)，依次訪問(wèn)V的各個(gè)未曾被訪問(wèn)過(guò)的鄰接點(diǎn)w1,w2,wt,然后再順序訪問(wèn)w1,w2,wt，的所有還為訪問(wèn)過(guò)的鄰接點(diǎn)。再?gòu)倪@些頂點(diǎn)

7、出發(fā)，訪問(wèn)它們還未訪問(wèn)過(guò)的鄰接點(diǎn)，如此做下去，直到圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。2、1將沒(méi)有前驅(qū)入度為零的頂點(diǎn)進(jìn)棧。2從棧中退出棧頂元素輸出，并把該頂點(diǎn)引出的所有弧刪去，即把它的各個(gè)鄰接點(diǎn)的入度減1，同時(shí)將當(dāng)前已輸出的頂點(diǎn)個(gè)數(shù)加1.3將新的入度為零的頂點(diǎn)再進(jìn)棧。4重復(fù)2、2兩步，直到棧為空為止。此時(shí)或者已經(jīng)輸出前部頂點(diǎn)，或者剩下的頂點(diǎn)中沒(méi)有入度為零的頂點(diǎn)。3、設(shè)置一個(gè)n*n的矩陣Ak，其中除對(duì)角線元素為0外，其他元素A(k)ij表示頂點(diǎn)i到頂點(diǎn)j的路徑長(zhǎng)度，k表示運(yùn)算步驟。開場(chǎng)時(shí)k = -1,A(-1)ij = arcsij,即A為圖的鄰接矩陣。以后逐步嘗試在原路徑中參加其他頂點(diǎn)作為中間點(diǎn)，如果

8、增加中間點(diǎn)頂點(diǎn)后，得到的路徑比原來(lái)的路徑短，則以此新路徑代替原來(lái)路徑，修改矩陣元素。具體做法為：第0步讓所有路徑上參加中間點(diǎn)0，去Aij與Ai0 + Aoj中較小的值作Aij的新值，完成后得到A(0)如此進(jìn)展下去，當(dāng)?shù)趎-1步完成后，得到A(n-1),A(n-1)即為所求的結(jié)果，A(n-1)ij表示從i到j(luò)路徑上的中間頂點(diǎn)的序號(hào)小于或等于n-1的最短路徑的長(zhǎng)度，即A(n-1)ij表示從i到j(luò)的最短路徑的長(zhǎng)度。算法的實(shí)現(xiàn)和測(cè)試結(jié)果：包括算法運(yùn)行時(shí)的輸入、輸出，實(shí)驗(yàn)中出現(xiàn)的問(wèn)題及解決方法等1、2、3、算法時(shí)間復(fù)雜度分析1、深度優(yōu)先遍歷：On*n.廣度優(yōu)先遍歷：On*n.2、On+e.3、O(n*n

9、*n).四、收獲與體會(huì)不想說(shuō)什么，這章的程序太難了，每次一想起來(lái)數(shù)據(jù)構(gòu)造還沒(méi)做就煩，前兩個(gè)題根本上一天能做一道題，第三題也就是騙騙OJ，實(shí)際上還有個(gè)小BUG，等有空再寫個(gè)真正符合題意的程序吧。五、源代碼清單1、#includeusingnamespace std;#define INFINITY INT_MA*#define MA*_VERTE*_NUM 20/typedef enum DG,DN,AG,ANGraphKind;typedefint Elemtype;typedefstruct QueueNodeElemtype data;struct QueueNode *ne*t;Queu

10、eNode;typedefstruct QueueListQueueNode *front;QueueNode *rear;QueueList;QueueList *CreateQueue()QueueList *Q;QueueNode *p;Q = (QueueList*)malloc(sizeof(QueueList);p = (QueueNode*)malloc(sizeof(QueueNode);Q-front = Q-rear = p;Q-front-ne*t = NULL;return Q;bool QueueEmpty(QueueList *Q)if(Q-front = Q-re

11、ar)returntrue;elsereturnfalse;QueueList *EnQueue(QueueList *Q,int element)QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode);p-data = element;p-ne*t = NULL;Q-rear-ne*t = p;Q-rear = p;return Q; QueueList *DeQueue(QueueList *Q,Elemtype *e)QueueNode *temp;if(!QueueEmpty(Q)temp = Q-front-ne*t;*e = te

12、mp-data;Q-front-ne*t = temp-ne*t;if(Q-rear = temp)Q-rear = Q-front;free(temp);return Q;void display(QueueList *Q)QueueNode *temp;temp = Q-front;if(!QueueEmpty(Q)while(temp-ne*t != NULL)temp = temp-ne*t;cout data endl;typedefstruct Arc int adj;Arc,AdjMatri*MA*_VERTE*_NUMMA*_VERTE*_NUM;typedefstruct i

13、nt verte*MA*_VERTE*_NUM;AdjMatri* arcs;int ve*num,arum;/GraphKind kind;Graph;void CreateAG(Graph &G,int n,int m)int i,j;G.ve*num = n;G.arum = m;for(i = 0;i n;i+)G.verte*i = i + 1;for(i = 0;i n;i+)for(j = 0;j n;j+)G.arcsij.adj = 0;for(int k = 0;k i j;G.arcsi-1j-1.adj = G.arcsj-1i-1.adj = 1;bool visit

14、edMA*_VERTE*_NUM;int count = 0;void DFS(Graph G,int v)visitedv-1 = true;count+;cout v;if(count G.ve*num)cout ;for(int i = v;i G.ve*num;i+)if(G.arcsv-1i.adj != 0 & !visitedi)DFS(G,G.verte*i);void DFSTraverse(Graph G)int v = 0;for(v = 0;v G.ve*num;v+)visitedv = false;v = 1;/遍歷入口點(diǎn)DFS(G,v);void BFS(Grap

15、h G)int i,j;int k = 0;int v = 0;int u = 0;for(v = 0;v G.ve*num;v+)visitedv = false;QueueList *queue;queue = CreateQueue();v = 1;EnQueue(queue,v);visitedv-1 = true;while(!QueueEmpty(queue)DeQueue(queue,&u);k+;cout u;if(k G.ve*num)cout ;for(int i = u;i n m;CreateAG(G1,n,m);DFSTraverse(G1);cout endl;BF

16、S(G1);return 0;2、#includeusingnamespace std;#define INFINITY INT_MA*#define MA*_VERTE*_NUM 20typedefint Elemtype;typedefstruct QueueNodeElemtype data;struct QueueNode *ne*t;QueueNode;typedefstruct QueueListQueueNode *front;QueueNode *rear;QueueList;QueueList *CreateQueue()QueueList *Q;QueueNode *p;Q

17、 = (QueueList*)malloc(sizeof(QueueList);p = (QueueNode*)malloc(sizeof(QueueNode);Q-front = Q-rear = p;Q-front-ne*t = NULL;return Q;bool QueueEmpty(QueueList *Q)if(Q-front = Q-rear)returntrue;elsereturnfalse;QueueList *EnQueue(QueueList *Q,int element)QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueN

18、ode);p-data = element;p-ne*t = NULL;Q-rear-ne*t = p;Q-rear = p;return Q; QueueList *DeQueue(QueueList *Q,Elemtype *e)QueueNode *temp;if(!QueueEmpty(Q)temp = Q-front-ne*t;*e = temp-data;Q-front-ne*t = temp-ne*t;if(Q-rear = temp)Q-rear = Q-front;free(temp);return Q;void display(QueueList *Q)QueueNode

19、*temp;temp = Q-front;if(!QueueEmpty(Q)while(temp-ne*t != NULL)temp = temp-ne*t;cout data endl;typedefstruct Arode int adjve*;struct Arode *ne*tarc;Arode;typedefstruct VNode int data;Arode *firstarc;VNode,AdjListMA*_VERTE*_NUM;typedefstruct AdjList verte*;int ve*num,arum;/GraphKind kind;Graph;void Cr

20、eateDN(Graph &G,int e,int n)int i,j;G.ve*num = n;G.arum = e;for(i = 0;i n;i+)G.verte*i.data = i+1;G.verte*i.firstarc = NULL;for(int k = 0;k i j;Arode *s,*p;s = (Arode*)malloc(sizeof(Arode);s-adjve* = j-1;s-ne*tarc = NULL;if(G.verte*i-1.firstarc = NULL)G.verte*i-1.firstarc = s;elsep = G.verte*i-1.fir

21、starc;while(p -ne*tarc!= NULL)p =p-ne*tarc;p-ne*tarc = s;void FindInDegree(Graph G,int indegree)int i;Arode *p;for(i = 0;i G.ve*num;i+)indegreei = 0;for(i = 0;i adjve*+;p = p-ne*tarc;void TopologicalSort(Graph G)int i,k,count,indegreeMA*_VERTE*_NUM;bool visitedMA*_VERTE*_NUM;for(i = 0;i G.ve*num;i+)

22、visitedi = false;Arode *p;count = 0;FindInDegree(G,indegree);while(count G.ve*num)for(i = 0;i G.ve*num;i+)if(indegreei = 0 & visitedi = false)cout G.verte*i.data;if(count G.ve*num-1)cout ne*tarc)k = p-adjve*;indegreek-;break;int main()int n;/節(jié)點(diǎn)數(shù)int m;/關(guān)系數(shù)cin n m;Graph G1;CreateDN(G1,m,n);Topological

23、Sort(G1);return 0;3、#includeusingnamespace std;#define INFINITY 1000#define MA*_VERTE*_NUM 20typedefint Elemtype;typedefint Elemtype;typedefstruct QueueNodeElemtype data;struct QueueNode *ne*t;QueueNode;typedefstruct QueueListQueueNode *front;QueueNode *rear;QueueList;QueueList *CreateQueue()QueueLi

24、st *Q;QueueNode *p;Q = (QueueList*)malloc(sizeof(QueueList);p = (QueueNode*)malloc(sizeof(QueueNode);Q-front = Q-rear = p;Q-front-ne*t = NULL;return Q;bool QueueEmpty(QueueList *Q)if(Q-front = Q-rear)returntrue;elsereturnfalse;QueueList *EnQueue(QueueList *Q,int element)QueueNode *p;p = (QueueNode*)

25、malloc(sizeof(QueueNode);p-data = element;p-ne*t = NULL;Q-rear-ne*t = p;Q-rear = p;return Q; QueueList *DeQueue(QueueList *Q,Elemtype *e)QueueNode *temp;if(!QueueEmpty(Q)temp = Q-front-ne*t;*e = temp-data;Q-front-ne*t = temp-ne*t;if(Q-rear = temp)Q-rear = Q-front;free(temp);return Q;void display(Que

26、ueList *Q)QueueNode *temp;temp = Q-front;if(!QueueEmpty(Q)while(temp-ne*t != NULL)temp = temp-ne*t;cout data endl;typedefstruct Arc int adj;Arc,AdjMatri*MA*_VERTE*_NUMMA*_VERTE*_NUM;typedefstruct int verte*MA*_VERTE*_NUM;AdjMatri* arcs;int ve*num,arum;/GraphKind kind;Graph;void CreateAN(Graph &G,int

27、 n,int m)int i,j;int w = 0;G.ve*num = n;G.arum = m;for(i = 0;i n;i+) G.verte*i = i+1;for(i = 0;i n;i+)for(j = 0;j n;j+)G.arcsij.adj = INFINITY;for(int k = 0;k i j w;if(G.arcsi-1j-1.adj w)G.arcsi-1j-1.adj = G.arcsj-1i-1.adj = w;void Floyd(Graph G,int n,int m)int i,j;int ma* = 0;int AMA*_VERTE*_NUMMA*

28、_VERTE*_NUM;int pathMA*_VERTE*_NUMMA*_VERTE*_NUM;for(i = 0;i n;i+)for(j = 0;j n;j+)Aij = G.arcsij.adj;if(Aij INFINITY) pathij = i;else pathij = 0;int t;int sum;for(i = 0;i n;i+)t = 0;sum = 0;for(j = 0;j n;j+)if(Aij = n-1 & sum 20)cout sum;e*it(0);elsecontinue;for(int k = 0;k n;k+)for(i = 0;i n;i+)for(j = 0;j n