數(shù)據(jù)結(jié)構(gòu)牛小飛2 圖的遍歷

1、圖的遍歷圖的遍歷深度優(yōu)先搜索廣度優(yōu)先搜索圖的遍歷小結(jié)和作業(yè)復(fù)習(xí)課堂練習(xí)圖的遍歷的應(yīng)用舉例(自學(xué))復(fù)習(xí)復(fù)習(xí)- -圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(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ǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)012345abcdef14043525011253bacdfe復(fù)習(xí)復(fù)習(xí)- -圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(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ǔ)結(jié)構(gòu)圖的

2、存儲(chǔ)結(jié)構(gòu)abecd0101234abcde32034abecd159721113201234abcde1 154 93 20 111 72 212 3復(fù)習(xí)復(fù)習(xí)- -圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)0101234abcde32034abecd圖的遍歷圖的遍歷定義：從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問一次的過程。用途：是解決圖的連通性、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。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訪問頂點(diǎn)訪問頂點(diǎn)v ; ;for (w1、w2、w3 )若若鄰接點(diǎn)鄰接點(diǎn)wi未被訪問未被訪問，則則從它出發(fā)進(jìn)行深度從它出發(fā)進(jìn)行深度優(yōu)先搜索歷。優(yōu)先搜索歷。深度遍歷序列：深度遍歷序列：v1v2v4v5v3v7v6v8v1 v2 v4 v8 v5 v6 v3 v7v1v2v4v5v3v7v6v8深度優(yōu)先搜索深度優(yōu)先搜索- -連通圖連通圖 v4v6v2v5v1v8v3v71、從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷2、對(duì)圖g深度優(yōu)先搜索得到的頂點(diǎn)序列不是唯一的？3、搜索過程中經(jīng)過的邊和所有的頂點(diǎn)構(gòu)成了圖的一棵生成樹。4、如何判別v的鄰接點(diǎn)是否被訪

4、問？ 為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪問標(biāo)志 visited”;深度優(yōu)先搜索深度優(yōu)先搜索- -連通圖連通圖 void dfs(int v) / 從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖 / dfs深度優(yōu)先搜索深度優(yōu)先搜索- -連通圖連通圖 vertexsv.visited = true;/對(duì)v的尚未訪問的鄰接頂點(diǎn)w遞歸調(diào)用dfsfor(w=firstadjvex(v); w=0; w=nextadjvex(v,w) if (vertexsw.visited=false) dfs(w);v1v2v3v4v5v1v2v8v5v6v4v2v8v8v3v1v6v7v3v8dfs(g, v1)v1v2v4v5v3v7

5、v6v8v1v2v4v5v3v7v6v8v7深度優(yōu)先搜索深度優(yōu)先搜索非連通圖非連通圖首先將圖中每個(gè)頂點(diǎn)的訪問標(biāo)志設(shè)為 fasle, 之后搜索圖中每個(gè)頂點(diǎ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; +v) vertexsv.visited = false; / 訪問標(biāo)志數(shù)組

6、初始化 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)v v0 0出發(fā)，并在訪問此頂點(diǎn)出發(fā)，并在訪問此頂點(diǎn)之后之后依次訪問依次訪問v v0 0的所有未被訪問過的鄰接點(diǎn)的所有未被訪問過的鄰接點(diǎn)2.2.然后然后按這些頂點(diǎn)被訪問的先后次序依次訪問按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)它們的鄰接點(diǎn)，直至圖中所有和，直至圖中所有和v

7、v0 0有路徑相通有路徑相通的頂點(diǎn)都被訪問到。的頂點(diǎn)都被訪問到。3.3.若此時(shí)圖中尚有頂點(diǎn)未被訪問若此時(shí)圖中尚有頂點(diǎn)未被訪問, ,則另選圖中則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)4.4.重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止到為止廣度優(yōu)先搜索廣度優(yōu)先搜索v1v2v4v5v3v7v6v8v1v8廣度遍歷序列：廣度遍歷序列：v4v6v8v2v5v1v3v7 v2 v3 v4 v5 v6 v7廣度優(yōu)先搜索廣度優(yōu)先搜索v1v2v4v5v3v7v6v8v1v2v4v5v3v7v6v8v1v8廣度遍歷序列：廣度遍歷序列： v2 v3

8、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); /if /while /if課堂練習(xí)課堂練習(xí)1：無向圖g=(v,e),其中：

9、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：已知一無向圖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開始遍歷圖，得到的序列為abecd，則采用的是_。課堂練習(xí)課堂練習(xí)adbec圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例1.1.求一條求一條從頂點(diǎn)從頂點(diǎn)i i到頂點(diǎn)

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

11、舉例圖的遍歷應(yīng)用舉例1. 從頂點(diǎn) i 到頂點(diǎn)s ,若存在路徑，則從頂點(diǎn) i 出發(fā)進(jìn)行深度優(yōu)先搜索，必能搜索到頂點(diǎn)s 。4. 簡(jiǎn)單路徑可能有多條。3. 由它出發(fā)進(jìn)行的深度優(yōu)先遍歷已經(jīng)完成的頂點(diǎn)不是路徑上的頂點(diǎn)。結(jié)論：結(jié)論：2. 遍歷過程中搜索到的頂點(diǎn)不一定是路徑上的頂點(diǎn)。圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例void dfsearch( int v, int s, char *path) / 從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖g， / 求得一條從v到s的簡(jiǎn)單路徑，并記錄在path中 vertexsv.visited=true; = true; / 訪問第 v 個(gè)頂點(diǎn) for (w=firstadjv

12、ex(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=s) found = true; append(path, w); else if (!found) delete (path); / 從路徑上刪除頂點(diǎn) v 圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例2.2.求兩個(gè)頂點(diǎn)之間的一條求兩個(gè)頂點(diǎn)之間的一條長(zhǎng)度最短長(zhǎng)度最短的路的路徑徑 若兩個(gè)頂點(diǎn)之間存在多條路徑，則其中必有一條路徑長(zhǎng)度最短的路徑。如何求得這條路徑?圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例abchdekfg求從頂點(diǎn)b b到頂點(diǎn)k k的一條路徑長(zhǎng)度最短的路徑。圖的遍歷應(yīng)用舉例圖的遍歷應(yīng)用舉例abchdekfgabchdekfg廣度優(yōu)先搜索訪問頂點(diǎn)的次序是按廣度優(yōu)先搜索訪問頂點(diǎn)的次序是按“路徑長(zhǎng)度路徑長(zhǎng)度”漸增的次序漸增的次序。廣度優(yōu)先搜