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

1、實(shí)驗(yàn)報(bào)告學(xué)院（系）名稱： 計(jì)算機(jī)與通信工程學(xué)院姓名*學(xué)號(hào)*專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)2015級(jí)*班實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)四：圖的深度優(yōu)先與廣度優(yōu)先遍歷課程名稱數(shù)據(jù)結(jié)構(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)過程25分程序運(yùn)行20分回答問題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)度、編 寫程序過程 等內(nèi)容等。功能完善，功能不全有小錯(cuò)無法運(yùn)行O正確o基本正確O有提示o無法回答o完整o較完整o般o內(nèi)容極少o無報(bào)告o有o無o有o無一、實(shí)驗(yàn)?zāi)康睦斫鈭D的邏輯特點(diǎn)；

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

3、 define MAX_VERTEX_NUM 8頂點(diǎn)最大個(gè)數(shù)typedef struct ArcNode int adjvex;struct ArcNode *nextarc;int weight; / 邊的權(quán) ArcNode; / 表結(jié)點(diǎn) # define VertexType int II 頂點(diǎn)元素類型 typedef struct VNode int degree,indegree; II頂點(diǎn)的度，入度 VertexType data;ArcNode *firstarc; Vnode I* 頭結(jié)點(diǎn) *I; typedef structVnode verticesMAX_VERTEX_NU

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

5、數(shù)不超過10個(gè)，網(wǎng)中邊的權(quán)值設(shè)置成小于100。三、實(shí)驗(yàn)過程與實(shí)驗(yàn)結(jié)果應(yīng)包括如下主要內(nèi)容：數(shù)據(jù)結(jié)構(gòu)定義圖是由定點(diǎn)集合及定點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)，其形式化定義為Graph =（V,E）其中，V = x|x 某個(gè)數(shù)據(jù)對(duì)象是定點(diǎn)的有限非空集合； E = （x,y） |x,y V A Path（x,y）是頂點(diǎn)之間關(guān)系的有限集合，叫做便集。集合E中的Path （x,y）表示頂點(diǎn)x和頂點(diǎn)y之間有一條直接連線，即（x,y）表示一條邊，它是有方向的。算法設(shè)計(jì)思路簡(jiǎn)介算法描述：可以用自然語言、偽代碼或流程圖等方式1、圖的深度優(yōu)先搜索：在訪問圖中某一起始點(diǎn)V后，由V出發(fā)，訪問它的任一鄰接頂點(diǎn)w1;再?gòu)膚1

6、;出發(fā)，訪問與w1鄰接但還沒有訪問過得頂點(diǎn)w2 ;然后再?gòu)膚2出發(fā)，進(jìn)行類似的訪問，,如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn)u為止；接著退回一步，回溯到 u的前一個(gè)鄰接頂點(diǎn)，看它是否還有其他沒有被訪問過的鄰接點(diǎn)。如果有，則訪問此鄰接點(diǎn)，之后再?gòu)?此頂點(diǎn)出發(fā)，進(jìn)行與前述類似的訪問；如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程， 直至圖中所有和 V連通的頂點(diǎn)都被訪問到。若此時(shí)圖中尚有頂點(diǎn)未被訪問，則說明該圖不是連通圖，另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被 訪問過為止。圖的廣度優(yōu)先搜索：使用廣度優(yōu)先搜索（BFS）在訪問了起始頂點(diǎn)V之后，由V出發(fā)，依次

7、訪問 V的各個(gè)未曾被訪問過的鄰接點(diǎn) w1,w2,wt,然后再順序訪問 w1,w2,wt，的所有還為訪問過的鄰接點(diǎn)。再?gòu)倪@些頂點(diǎn)出發(fā)，訪問它們還未訪問過的鄰接點(diǎn)，如此做下去，直到圖中所有頂點(diǎn)都被訪問過為止。2、（1）將沒有前驅(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)中沒有入度為零的頂點(diǎn)。3、設(shè)置一個(gè)n*n的矩陣A（ k ），其中除對(duì)角線元素為0夕卜，其他元素 A（k）ij

8、表示頂點(diǎn)i到頂點(diǎn)j的路徑長(zhǎng)度，k表示運(yùn)算步驟。開始時(shí)k = -1,A（-1）ij = arcsij,即A為圖的鄰接矩陣。以后逐步嘗試在原路徑中加入其他頂點(diǎn)作為中間點(diǎn)，如果增加中間點(diǎn)頂點(diǎn)后，得到的路徑比 原來的路徑短，則以此新路徑代替原來路徑，修改矩陣元素。具體做法為：第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)度。算法的

9、實(shí)現(xiàn)和測(cè)試結(jié)果：包括算法運(yùn)行時(shí)的輸入、輸出，實(shí)驗(yàn)中出現(xiàn)的問題及解決辦法等1、6 61 21 32 43 44 54 61 2 4 5 6 31 2 3 4 5 6請(qǐng)按任意鍵繼續(xù).C :WI N DOWSsystc m 3 2c md. cxe1 61 22 33 41 55 66 712 3 15 6 712 5 3 6 4 了請(qǐng)按任靈犍繼續(xù).C3B C:QVINDOW£syyt(?nn32(:mdcc62 3 4 5 62 3 4 5 6請(qǐng)按仟竜鍵紳續(xù).”3J C AWIN D 0V/Ssyste m 32c m d >exe7 67 45 44 22 11 31 65 7

10、4 2 1 3 6請(qǐng)按任豈鍵繼續(xù)一SB 匚:WI N DOWStyste m i 2c m d. exe5 41 22 33 44 51 2 3 4 5請(qǐng)按任薫憔綻綻.SS C:WINDOWSsystem3cnnd.exe3 66 56 45 14 23 6 4 2 5 l請(qǐng)按任意健繼續(xù).31 C AWI IM D O WSsy s te in 3 2c md. exe6 5C 44 34 23 12 56 4 2 3 1 "青按任意腱醴續(xù)Sfl C :WI N DOWSsyste m 32c m d .cxe5 41 22 35 44 312 5 4 3請(qǐng)按任意鍵繼續(xù).3、|SB

11、C :WI N DOWStyste m 3 2c m d.«4 41 2 11 3 23 4 3E 4 46請(qǐng)按仟袁錦樂續(xù)311 C:WI N DOWSsystem32c md.c4 41 2 11 2 21 3 61 4 714請(qǐng)按ft意健繼續(xù).SB C :WI N D OWSsyste m 3 2c md. exc1 2 12 3 23 4 34 5 45 6 53 7 17 4 114詩(shī)按任意譴窒換.C AWIN D OWSsyste m 3 2c md. exe4 51 2 92 4 83 4 71 3 63 2 619請(qǐng)按仕意遵繼續(xù)1 0u請(qǐng)按任意鍵繼續(xù).算法時(shí)間復(fù)雜度分析

12、1、深度優(yōu)先遍歷：0 (n*n ).廣度優(yōu)先遍歷：0 (n*n ).2、0 (n+e).3、O(n*n*n).四、收獲與體會(huì)不想說什么，這章的程序太難了，每次一想起來數(shù)據(jù)結(jié)構(gòu)還沒做就煩，前兩個(gè)題基本上一天能做一道題, 第三題也就是騙騙 0J,實(shí)際上還有個(gè)小 BUG，等有空再寫個(gè)真正符合題意的程序吧。五、源代碼清單1、#in clude<iostream> usingn amespacestd;#defi ne INFINITY INT_MAX#defi ne MAX_VERTEX_NUM 20/typedef e num DG,DN,AG,ANGraphK ind; typedef

13、i nt Elemtype;typedefstruct QueueNodeElemtype data; struct QueueNode *n ext;QueueNode; typedefstruct QueueList QueueNode *front;QueueNode *rear;QueueList;QueueList *CreateQueue() QueueList *Q;QueueNode *p;Q = (QueueList*)malloc( sizeof(QueueList); p = (QueueNode*)malloc(sizeof(QueueNode); Q->fron

14、t = Q->rear = p;Q->fro nt->n ext = NULL; return Q;bool QueueEmpty(QueueList *Q)if(Q->fro nt = Q->rear) returntrue;elsereturnfalse;QueueList *En Queue(QueueList *Q, int eleme nt)QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode); p->data = eleme nt;p->n ext = NULL;Q->rear-

15、>n ext = p;Q->rear = p; return Q;QueueList *DeQueue(QueueList *Q,Elemtype *e) QueueNode *temp; if(!QueueEmpty(Q)Jtemp = Q->fro nt->next;*e = temp->data;Q->fro nt->n ext = temp->next;if (Q->rear = temp)Q->rear = Q->fro nt; free(temp);return Q;void display(QueueList *Q

16、)QueueNode *temp; temp = Q->fro nt; if(!QueueEmpty(Q)while(temp->next != NULL)temp = temp->n ext; cout << temp->data << en dl;typedefstruct Arc int adj; Arc,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedefstruct in t vertexMAX_VERTEX_NUM;AdjMatrix arcs;int vex nu m,arc num;/ Gr

17、aphKi nd kind;Graph;void CreateAG(Graph &G, int n,int m)int i,j;G.vex num = n;G.arc num 二 m;for(i = 0;i < n ;i+)G.vertexi = i + 1;for(i = 0;i < n ;i+)for(j = 0;j < n;j+) G.arcsij.adj = 0;for(int k = 0;k < m;k+)cin >> i >> j;G.arcsi-1j-1.adj = G.arcsj-1i-1.adj = 1;bool vis

18、itedMAX_VERTEX_NUM;int count = 0;void DFS(Graph G,i nt v)visitedv-1 = true; coun t+; cout << v;if (count < G.vexnum)cout <<""for(i nt i = v;i < G.vex nu m;i+)if (G.arcsv-1i.adj != 0 && !visitedi) DFS(G,G.verte xi);void DFSTraverse(Graph G)int v = 0;for(v = 0;v <

19、; G.vex nu m;v+) visitedv = false;v = 1;/遍歷入口點(diǎn)DFS(G,v);void BFS(Graph G)int i,j;int k = 0;int v = 0;int u = 0;for(v = 0;v < G.vex nu m;v+) visitedv = false;QueueList *queue; queue = CreateQueue();v = 1;En Queue(queue,v); visitedv-1 = true; while(!QueueEmpty(queue) DeQueue(queue，&u);k+;cout &l

20、t;< u;if (k < G.vex num) cout <<""for(i nt i = u;i < G.vex nu m;i+) if(G.arcsu-1i.adj != 0 && !visitedi)En Queue(queue,G.vertexi); visitedi = true;int mai n()Graph G1;int m = 0;/ 邊數(shù)int n二0;/頂點(diǎn)數(shù)cin >> n >> m;CreateAG(G1, n,m); DFSTraverse(G1); cout <<

21、; en dl;BFS(G1); return 0;2、#in clude<iostream> usingn amespacestd;#defi ne INFINITY INT_MAX#defi ne MAX_VERTEX_NUM 20 typedefi nt Elemtype; typedefstruct QueueNode Elemtype data; struct QueueNode *n ext;QueueNode;typedefstruct QueueListQueueNode *front;QueueNode *rear;QueueList;QueueList *Cre

22、ateQueue()QueueList *Q;QueueNode *p;Q = (QueueList*)malloc( sizeof(QueueList); p = (QueueNode*)malloc(sizeof(QueueNode); Q->front = Q->rear = p;Q->fro nt->n ext = NULL; return Q;bool QueueEmpty(QueueList *Q)if (Q->fro nt 二二 Q->rear)returntrue;elsereturnfalse;QueueList *En Queue(Que

23、ueList *Q, int eleme nt) QueueNode *p;p = (QueueNode*)malloc(sizeof(QueueNode); p->data = eleme nt;p->n ext = NULL;Q->rear- >n ext = p;Q->rear = p; return Q;QueueList *DeQueue(QueueList *Q,Elemtype *e) QueueNode *temp;if(!QueueEmpty(Q)temp = Q->fro nt->next;*e = temp->data;Q-

24、>fro nt->n ext = temp->next;if (Q->rear = temp)Q->rear = Q->fro nt; free(temp);return Q;void display(QueueList *Q)QueueNode *temp; temp = Q->fro nt;if(!QueueEmpty(Q)while(temp->next != NULL)temp = temp->n ext;cout << temp->data << en dl; typedefstruct ArcNod

25、e int adjvex;struct ArcNode *n extarc;ArcNode;typedefstruct VNode int data;ArcNode *firstarc;VNode,AdjListMAX VERTEX NUM:typedefstruct AdjList vertex;int vex nu m,arc num;/GraphKi nd kind;Graph;void CreateDN(Graph &G, int ejnt n)int i,j;G.vex num = n;G.arc num 二 e;for(i = 0;i <n ;i+)G.vertexi

26、.data = i+1; G.verte xi .firstarc = NULL;for(i nt k = 0;k < e;k+)cin >> i >> j;ArcNode *s,*p;s = (ArcNode*)malloc( sizeof(ArcNode); s->adjvex = j-1;s->n extarc = NULL;if (G.verte xi-1.firstarc = NULL)G.vertexi-1.firstarc = s;elsep = G.vertexi-1.firstarc; while (p ->n extarc!=

27、 NULL) p =p->n extarc;p->n extarc = s;void Findln Degree(Graph G,i nt in degree)int i;ArcNode *p;for(i = 0;i < G.vex nu m;i+)in degreei = 0;for(i = 0;i < G.vex nu m;i+)p = G.vertexi.firstarc;while(p)in degreep->adjvex+:p = p->n extarc;void TopologicalSort(Graph G)int i,k,count,inde

28、greeMAX_VERTEX_NUM;bool visitedMAX_VERTEX_NUM;for(i = 0;i < G.vex nu m;i+) visitedi = false;ArcNode *p;count = 0;Findln Degree(G,i ndegree); while(co unt < G.vex num) for(i = 0;i < G.vex nu m;i+)if(i ndegreei = 0 && visitedi = false) cout << G.vertexi.data;if (count < G.vex

29、num-1) cout <<""coun t+;visitedi = true;for(p = G.vertexi.firstarc;p;p = p->n extarc) k = p->adjvex;in degreek-; break;int mai n()int n;/節(jié)點(diǎn)數(shù)int m;/關(guān)系數(shù)cin >> n >> m;Graph G1;CreateDN(G1,m, n);TopologicalSort(G1); return 0;#in clude<iostream>3、usingn amespacestd

30、; #defi ne INFINITY 1000 #defi ne MAX_VERTEX_NUM 20 typedefi nt Elemtype; typedefi nt Elemtype; typedefstruct QueueNodeElemtype data; struct QueueNode *n ext;QueueNode; typedefstruct QueueList QueueNode *front;QueueNode *rear; QueueList;QueueList *CreateQueue() QueueList *Q;QueueNode *p;Q = (QueueLi

31、st*)malloc( sizeof(QueueList); p = (QueueNode*)malloc(sizeof(QueueNode); Q->front = Q->rear = p;Q->fro nt->n ext = NULL;return Q;bool QueueEmpty(QueueList *Q) if(Q->fro nt = Q->rear) returntrue;elsereturnfalse;QueueList *En Queue(QueueList *Q, int eleme nt) QueueNode *p;p = (QueueN

32、ode*)malloc(sizeof(QueueNode); p->data = eleme nt;p->n ext = NULL;Q->rear- >n ext = p;Q->rear = p; return Q;QueueList *DeQueue(QueueList *Q,Elemtype *e) QueueNode *temp;if(!QueueEmpty(Q)temp = Q->fro nt->n ext; *e 二 temp->data:Q->fro nt->n ext = temp->next;if (Q->

33、rear = temp) Q->rear = Q->fro nt;free(temp);return Q;void display(QueueList *Q)QueueNode *temp; temp = Q->fro nt; if(!QueueEmpty(Q)while(temp->next != NULL)temp = temp->n ext; cout << temp->data << en dl;typedefstruct Arc int adj; Arc,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_N

34、UM; typedefstruct in t vertexMAX_VERTEX_NUM;AdjMatrix arcs;int vex nu m,arc num;/ GraphKi nd kind;Graph;void CreateAN(Graph &G, int n,int m)int i,j;int w = 0;G.vex num = n;G.arc num 二 m;for(i = 0;i < n ;i+)G.vertexi = i+1;for(i = 0;i < n ;i+)for(j = 0;j < n;j+) G.arcsij.adj = INFINIT Y;

35、for(int k = 0;k < m;k+)cin >> 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,i nt n ,i nt m)int i,j;int max = 0;int AMAX_VERTEX_NUMMAX_VERTEX_NUM;int pathMAX_VERTEX_NUMMAX_VERTEX_NUM; for(i = 0;i < n ;i+)for(j = 0;j < n;j

36、+)Aij = G.arcsij.adj;if(Aij < INFINIT Y) 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 < 1000) t+;sum = sum + Aij;if(t >= n-1 && sum < 20)cout << sum; exit(0);elsecon ti nue;for(i nt k = 0;k < n ;k+) for(i = 0

37、;i < n ;i+) for(j = 0;j < n;j+) if(Aik + Akj < Aij) Aij = Aik + Akj; pathij = pathkj;/cout << "處？理 O'a后 '?" << endl;for(i 二 0;i < n:i+)/ for(j = 0;j < n;j+)/if(Aij < INFINIT Y)/cout << Aij << "t"/else/cout << 0 << "t&