數(shù)據(jù)結(jié)構(gòu)2 圖的遍歷ppt課件

1、圖的遍歷圖的遍歷深度優(yōu)先搜索廣度優(yōu)先搜索圖的遍歷小結(jié)和作業(yè)復(fù)習(xí)課堂練習(xí)圖的遍歷的運(yùn)用舉例(自學(xué))復(fù)習(xí)復(fù)習(xí)- -圖的存儲(chǔ)構(gòu)造圖的存儲(chǔ)構(gòu)造BACDFE0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 復(fù)習(xí)復(fù)習(xí)- -圖的存儲(chǔ)構(gòu)造圖的存儲(chǔ)構(gòu)造012345ABCDEF14043525011253BACDFE復(fù)習(xí)復(fù)習(xí)- -圖的存儲(chǔ)構(gòu)造圖的存儲(chǔ)構(gòu)造ABECD0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 ABECD1597211132復(fù)習(xí)復(fù)習(xí)- -圖的存儲(chǔ)構(gòu)造圖的

2、存儲(chǔ)構(gòu)造ABECD0101234ABCDE32034ABECD159721113201234ABCDE1 154 93 20 111 72 212 3復(fù)習(xí)復(fù)習(xí)- -圖的存儲(chǔ)構(gòu)造圖的存儲(chǔ)構(gòu)造0101234ABCDE32034ABECD圖的遍歷圖的遍歷定義：從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其他頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問(wèn)一次的過(guò)程。用途：是處理圖的連通性、拓?fù)渑判蚝颓箨P(guān)鍵途徑等算法的根底。u深度優(yōu)先搜索u廣度優(yōu)先搜索分類：深度優(yōu)先搜索深度優(yōu)先搜索SG1SG2SG3W1、W2和W3 均為 V 的鄰接點(diǎn)，SG1、SG2 和 SG3 分別為含頂點(diǎn)W1、W2和W3 的子圖。Vw1w3w2深度優(yōu)先搜

3、索深度優(yōu)先搜索SG1SG2SG3Vw1w3w2訪問(wèn)頂點(diǎn)訪問(wèn)頂點(diǎn)V ;V ;for (W1for (W1、W2W2、W3 )W3 )假設(shè)鄰接點(diǎn)假設(shè)鄰接點(diǎn)WiWi未被訪未被訪問(wèn)，那么從它出發(fā)進(jìn)問(wèn)，那么從它出發(fā)進(jìn)展深度優(yōu)先搜索歷。展深度優(yōu)先搜索歷。深度遍歷序列：深度遍歷序列：V1V2V4V5V3V7V6V8V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8深度優(yōu)先搜索深度優(yōu)先搜索- -連通圖連通圖 V4V6V2V5V1V8V3V71、從深度優(yōu)先搜索遍歷連通圖的過(guò)程類似于樹(shù)的先根遍歷2、對(duì)圖G深度優(yōu)先搜索得到的頂點(diǎn)序列不是獨(dú)一的？3、搜索過(guò)程中經(jīng)過(guò)的邊和一切的頂點(diǎn)構(gòu)成了圖的

4、一棵生成樹(shù)。4、如何判別V的鄰接點(diǎn)能否被訪問(wèn)？ 為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪問(wèn)標(biāo)志 visited;深度優(yōu)先搜索深度優(yōu)先搜索- -連通圖連通圖 void DFS(int v) / 從頂點(diǎn)從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖出發(fā)，深度優(yōu)先搜索遍歷連通圖 / DFS深度優(yōu)先搜索深度優(yōu)先搜索- -連通圖連通圖 vertexsv.visited = true;/對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w遞歸調(diào)用DFSfor(w=firstAdjVex(v); w=0; w=nextAdjVex(v,w) if (vertexsw.visited=false) DFS(w);V1V2V3V4V5V1V2V8V5V6V4V2V

5、8V8V3V1V6V7V3V8DFS(G, V1)V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V7深度優(yōu)先搜索深度優(yōu)先搜索非連通圖非連通圖首先將圖中每個(gè)頂點(diǎn)的訪問(wèn)標(biāo)志設(shè)為 fasle, 之后搜索圖中每個(gè)頂點(diǎn)，假設(shè)未被訪問(wèn)，那么以該頂點(diǎn)為起始點(diǎn)，進(jìn)展深度優(yōu)先搜索遍歷，否那么繼續(xù)檢查下一頂點(diǎn)。V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8深度遍歷：深度遍歷：V1 V2 V4 V8V5V3 V6 V7深度優(yōu)先搜索深度優(yōu)先搜索非連通圖非連通圖深度優(yōu)先搜索深度優(yōu)先搜索非連通圖非連通圖void DFSTraverse(int v) for (v=0; vvexNum;

6、 +v) vertexsv.visited = false; / 訪問(wèn)標(biāo)志數(shù)組初始訪問(wèn)標(biāo)志數(shù)組初始化化 for (v=0; vw1, V-w2, V-w8 的的途徑長(zhǎng)度為途徑長(zhǎng)度為1;V-w7, V-w3, V-w5的的途徑長(zhǎng)度為途徑長(zhǎng)度為2;V-w6, V-w4的途徑長(zhǎng)度為的途徑長(zhǎng)度為3。w1w8w3w7w6w2w5w4廣度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索1.1.從圖中的某個(gè)頂點(diǎn)從圖中的某個(gè)頂點(diǎn)V0V0出發(fā)，并在訪問(wèn)此頂點(diǎn)出發(fā)，并在訪問(wèn)此頂點(diǎn)之后依次訪問(wèn)之后依次訪問(wèn)V0V0的一切未被訪問(wèn)過(guò)的鄰接點(diǎn)的一切未被訪問(wèn)過(guò)的鄰接點(diǎn)2.2.然后按這些頂點(diǎn)被訪問(wèn)的先后次序依次訪問(wèn)然后按這些頂點(diǎn)

7、被訪問(wèn)的先后次序依次訪問(wèn)它們的鄰接點(diǎn)，直至圖中一切和它們的鄰接點(diǎn)，直至圖中一切和V0V0有途徑相通有途徑相通的頂點(diǎn)都被訪問(wèn)到。的頂點(diǎn)都被訪問(wèn)到。3.3.假設(shè)此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)假設(shè)此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn), ,那么另選那么另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)4.4.反復(fù)上述過(guò)程，直至圖中一切頂點(diǎn)都被訪問(wèn)反復(fù)上述過(guò)程，直至圖中一切頂點(diǎn)都被訪問(wèn)到為止到為止廣度優(yōu)先搜索廣度優(yōu)先搜索V1V2V4V5V3V7V6V8V1V8廣度遍歷序列：廣度遍歷序列：V4V6V8V2V5V1V3V7 V2 V3 V4 V5 V6 V7廣度優(yōu)先搜索廣度優(yōu)先搜索V1V2V4V5V3V7V

8、6V8V1V2V4V5V3V7V6V8V1V8廣度遍歷序列：廣度遍歷序列： V2 V3 V4 V6 V7V5public void BFS() ArrayQueue AQueue=new ArrayQueue(); for(int i=0;ivexnum;i+) vertexsi.visited=false; for(int v=0;v=0; w=nextAdjVex(u,w) if (vertexs(w).wasVisited=false) System.out.print(vertexsw.data+ ); vertexs(w).visited=true; AQueue.enQueue(w

9、); /if /while /if課堂練習(xí)課堂練習(xí)1：無(wú)向圖G=(V,E),其中：V=a,b,c,d,e,f, E= (a,b), (a,e), (a,c), (b,e), (c,f), (f,d), (e,d)，對(duì)該圖進(jìn)展深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的 。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,babedcf2：知一無(wú)向圖G=V，E，其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開(kāi)場(chǎng)遍歷圖，得到的序列為abecd，那么采用的是_。課堂練習(xí)課堂練習(xí)adbec圖

10、的遍歷運(yùn)用舉例圖的遍歷運(yùn)用舉例1.1.求一條從頂點(diǎn)求一條從頂點(diǎn)i i到頂點(diǎn)到頂點(diǎn)s s的簡(jiǎn)單途徑的簡(jiǎn)單途徑2.2.求兩個(gè)頂點(diǎn)之間的一條長(zhǎng)度最短的途徑求兩個(gè)頂點(diǎn)之間的一條長(zhǎng)度最短的途徑圖的遍歷運(yùn)用舉例圖的遍歷運(yùn)用舉例1.1.求一條從頂點(diǎn)求一條從頂點(diǎn)i i到頂點(diǎn)到頂點(diǎn)s s的簡(jiǎn)單途徑的簡(jiǎn)單途徑求從頂點(diǎn)b到頂點(diǎn)k的一條簡(jiǎn)單途徑。abchdekfg從頂點(diǎn)b出發(fā)進(jìn)展深度優(yōu)先搜索遍歷圖的遍歷運(yùn)用舉例圖的遍歷運(yùn)用舉例求從頂點(diǎn)b到頂點(diǎn)k的一條簡(jiǎn)單途徑。假設(shè)找到的第一個(gè)鄰接點(diǎn)是a,且得到的結(jié)點(diǎn)訪問(wèn)序列為: b a c h d e k f g假設(shè)找到的第一個(gè)鄰接點(diǎn)是g,那么得到的結(jié)點(diǎn)訪問(wèn)序列為:b g f k e

11、 a d h cabchdekfg圖的遍歷運(yùn)用舉例圖的遍歷運(yùn)用舉例1. 從頂點(diǎn)從頂點(diǎn) i 到頂點(diǎn)到頂點(diǎn)s ,假設(shè)存在途徑，那么從頂假設(shè)存在途徑，那么從頂點(diǎn)點(diǎn) i 出發(fā)進(jìn)展深度優(yōu)先搜索，必能搜索到頂點(diǎn)出發(fā)進(jìn)展深度優(yōu)先搜索，必能搜索到頂點(diǎn)s 。4. 簡(jiǎn)單途徑能夠有多條。簡(jiǎn)單途徑能夠有多條。3. 由它出發(fā)進(jìn)展的深度優(yōu)先遍歷曾經(jīng)完成的由它出發(fā)進(jìn)展的深度優(yōu)先遍歷曾經(jīng)完成的頂點(diǎn)不是途徑上的頂點(diǎn)。頂點(diǎn)不是途徑上的頂點(diǎn)。結(jié)論：結(jié)論：2. 遍歷過(guò)程中搜索到的頂點(diǎn)不一定是途徑上的遍歷過(guò)程中搜索到的頂點(diǎn)不一定是途徑上的頂點(diǎn)。頂點(diǎn)。圖的遍歷運(yùn)用舉例圖的遍歷運(yùn)用舉例void DFSearch( int v, int s

12、, char *PATH) / 從第從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G， / 求得一條從求得一條從v到到s的簡(jiǎn)單途徑，并記錄在的簡(jiǎn)單途徑，并記錄在PATH中中 vertexsv.visited=true; = TRUE; / 訪問(wèn)第訪問(wèn)第 v 個(gè)個(gè)頂點(diǎn)頂點(diǎn) for (w=FirstAdjVex(G,v); w=0 ; w=NextAdjVex(G,v,w) ) if (! Vertexsw.visited) DFSearch(w, s, PATH); Append(PATH, getVertex(v); / 第v個(gè)頂點(diǎn)參與途徑&!foundif (w=

13、s) found = TRUE; Append(PATH, w); else if (!found) Delete (PATH); / 從途徑上刪除頂點(diǎn)從途徑上刪除頂點(diǎn) v 圖的遍歷運(yùn)用舉例圖的遍歷運(yùn)用舉例2.2.求兩個(gè)頂點(diǎn)之間的一條長(zhǎng)度最短的途求兩個(gè)頂點(diǎn)之間的一條長(zhǎng)度最短的途徑徑 假設(shè)兩個(gè)頂點(diǎn)之間存在多條途徑，那么其中必有一條途徑長(zhǎng)度最短的途徑。如何求得這條途徑?圖的遍歷運(yùn)用舉例圖的遍歷運(yùn)用舉例abchdekfg求從頂點(diǎn)b到頂點(diǎn)k的一條途徑長(zhǎng)度最短的途徑。圖的遍歷運(yùn)用舉例圖的遍歷運(yùn)用舉例abchdekfgabchdekfg廣度優(yōu)先搜索訪問(wèn)頂點(diǎn)的次序是按廣度優(yōu)先搜索訪問(wèn)頂點(diǎn)的次序是按“途途徑長(zhǎng)度漸增的次序。徑長(zhǎng)度漸增的