深度優(yōu)先搜索廣度優(yōu)先搜索

1、1,一、深度優(yōu)先搜索二、廣度優(yōu)先搜索,8.4 圖的遍歷,遍歷定義：從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊，訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，就叫做圖的遍歷，它是圖的基本運(yùn)算。,遍歷實(shí)質(zhì)：找每個(gè)頂點(diǎn)的鄰接點(diǎn)的過(guò)程。圖的特點(diǎn)：圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問過(guò)的頂點(diǎn)。,解決思路：可設(shè)置一個(gè)輔助數(shù)組 visited [n ]，用來(lái)標(biāo)記每個(gè)被訪問過(guò)的

2、頂點(diǎn)。它的初始狀態(tài)為0，在圖的遍歷過(guò)程中，一旦某一個(gè)頂點(diǎn)i 被訪問，就立即改 visited [i]為1，防止它被多次訪問。,圖常用的遍歷：,怎樣避免重復(fù)訪問？,2,一、深度優(yōu)先搜索( DFS ),基本思想：——仿樹的先序遍歷過(guò)程。,Depth_First Search,v1,DFS 結(jié)果,例1：,→,→,→,→,→,→,→,v2,v4,v8,v5,v3,v6,v7,,例2：,v2 → v1 → v3 → v5 →,DFS 結(jié)果,v4

3、→ v6,起點(diǎn),起點(diǎn),,,應(yīng)退回到V8，因?yàn)閂2已有標(biāo)記,,3,深度優(yōu)先搜索（遍歷）步驟：,詳細(xì)歸納：在訪問圖中某一起始頂點(diǎn) v 后，由 v 出發(fā)，訪問它的任一鄰接頂點(diǎn) w1；再?gòu)?w1 出發(fā)，訪問與 w1鄰接但還未被訪問過(guò)的頂點(diǎn) w2；然后再?gòu)?w2 出發(fā)，進(jìn)行類似的訪問，… 如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過(guò)的頂點(diǎn) u 為止。接著，退回一步，退到前一次剛訪問過(guò)的頂點(diǎn)，看是否還有其它未被訪問的鄰接頂點(diǎn)。

4、如果有，則訪問此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類似的訪問； 如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過(guò)程，直到連通圖中所有頂點(diǎn)都被訪問過(guò)為止。,,簡(jiǎn)單歸納： 訪問起始點(diǎn) v; 若v的第1個(gè)鄰接點(diǎn)沒訪問過(guò)，深度遍歷此鄰接點(diǎn)；若當(dāng)前鄰接點(diǎn)已訪問過(guò)，再找v的第2個(gè)鄰接點(diǎn)重新遍歷。,4,二、廣度優(yōu)先搜索( BFS ),基本思想：——仿樹的層次遍歷過(guò)程。,Breadth_First Search,v1,BFS 結(jié)果,例1：,

5、→,→,→,例2：,v3 →,BFS 結(jié)果,v4 → v5 →,起點(diǎn),起點(diǎn),v2 → v1 → v6 →,v9 → v8 → v7,5,廣度優(yōu)先搜索（遍歷）步驟：,簡(jiǎn)單歸納：在訪問了起始點(diǎn)v之后，依次訪問 v的鄰接點(diǎn)；然后再依次（順序）訪問這些點(diǎn)（下一層）中未被訪問過(guò)的鄰接點(diǎn)；直到所有頂點(diǎn)都被訪問過(guò)為止。,廣度優(yōu)先搜索是一種分層的搜索過(guò)程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個(gè)

6、遞歸的過(guò)程，其算法也不是遞歸的。,6,8.5 最小生成樹,1、生成樹：是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有n-1條邊。2、最小生成樹：如果無(wú)向連通圖是一個(gè)帶權(quán)圖，那么它的所有生成樹中必有一棵邊的權(quán)值總和為最小的生成樹，稱這棵生成樹為最小代價(jià)生成樹，簡(jiǎn)稱最小生成樹。,一、最小生成樹的基本概念,7,3.求最小生成樹,首先明確：使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹。按照生成樹的

7、定義，n 個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹肯定有 n 個(gè)頂點(diǎn)和僅僅n-1 條邊。,即有權(quán)圖,構(gòu)造最小生成樹的準(zhǔn)則必須只使用該網(wǎng)絡(luò)中的邊來(lái)構(gòu)造最小生成樹；必須使用且僅使用n-1條邊來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)；不能使用產(chǎn)生回路的邊。,目標(biāo)：在網(wǎng)絡(luò)的多個(gè)生成樹中，尋找一個(gè)各邊權(quán)值之和最小的生成樹。,8,欲在n個(gè)城市間建立通信網(wǎng)，則n個(gè)城市應(yīng)鋪n-1條線路；但因?yàn)槊織l線路都會(huì)有對(duì)應(yīng)的經(jīng)濟(jì)成本，而n個(gè)城市可能有n(n-1)/2 條線路，那么，如何選擇

8、n–1條線路使總費(fèi)用最少？,4、典型用途：,先建立數(shù)學(xué)模型：頂點(diǎn)———表示城市，有n個(gè)；邊————表示線路，有n–1條；邊的權(quán)值—表示線路的經(jīng)濟(jì)代價(jià)；連通網(wǎng)——表示n個(gè)城市間的通信網(wǎng)。,顯然此連通網(wǎng)是一棵生成樹！,問題抽象： n個(gè)頂點(diǎn)的生成樹很多，需要從中選一棵代價(jià)最小的生成樹，即該樹各邊的代價(jià)之和最小。此樹便稱為最小生成樹MST。,9,討論：如何求得最小生成樹？,最小生成樹（MST）的 性質(zhì)如下：,若U集是V的一個(gè)非空子集，若

9、(u0, v0)是一條最小權(quán)值的邊，其中u0?U，v0?V-U；則：(u0, v0)必在最小生成樹上。,設(shè)想一下：先把權(quán)值最小的邊歸入生成樹內(nèi)，逐個(gè)遞增，舍去回路邊，則得到的很可能就是最小生成樹！,求MST有多種算法，但最常用的是以下兩種：,Kruskal（克魯斯卡爾）算法Prim（普里姆）算法,Kruskal算法特點(diǎn)：將邊歸并，適于求稀疏網(wǎng)的最小生成樹。Prime算法特點(diǎn): 將頂點(diǎn)歸并，與邊數(shù)無(wú)關(guān)，適于稠密網(wǎng)。,對(duì)邊操作,對(duì)頂點(diǎn)操

10、作,10,二、普里姆算法,1、普里姆（Prim)算法思想 令集合U的初值為U={u0}，集合T={}。從所有結(jié)點(diǎn)u∈U和結(jié)點(diǎn)v∈V\U的帶權(quán)邊中選出具有最小權(quán)值的邊(u,v)，將結(jié)點(diǎn)v加入集合U中，將邊(u,v)加入集合T中。如此不斷重復(fù)，當(dāng)U=V時(shí)，最小生成樹便構(gòu)造完畢。,2、普利姆（Prim）算法示例： 歸并頂點(diǎn),1,2,,4,3,5,6,,,,,,,,,,6,1,6,5,5,5,6,3,4,2,最小代價(jià)生成樹,1,2,

11、,4,3,5,6,,,,,1,5,3,4,2,Prim算法是歸并頂點(diǎn)，適用于稠密網(wǎng)。,11,,例：利用普里姆算法構(gòu)造最小生成樹的過(guò)程,12,三、克魯斯卡爾（Kruska)算法,1、克魯斯卡爾算法思想 設(shè)無(wú)向連通帶權(quán)圖G=(V,E)，其中V為結(jié)點(diǎn)的集合，E為邊的集合。設(shè)帶權(quán)圖G的最小生成樹T由結(jié)點(diǎn)集合和邊的集合構(gòu)成，其初值為T=(V,{})，既初始時(shí)最小生成樹T只由帶權(quán)圖G中結(jié)點(diǎn)集合組成，各結(jié)點(diǎn)之間沒有一條邊。這樣，最小生成樹T

12、中的各個(gè)結(jié)點(diǎn)各自構(gòu)成一個(gè)連通分量。然后，按照邊的權(quán)值遞增的順序考察帶權(quán)圖G中邊集合E的各條邊，若被考察的邊的兩個(gè)結(jié)點(diǎn)屬于T的兩個(gè)不同的連通分量，則將此邊加入到最小生成樹T中，同時(shí)，把兩個(gè)連通分量連接為一個(gè)連通分量；若被考察的邊的兩個(gè)結(jié)點(diǎn)屬于T的同一個(gè)連通分量，則將此邊舍去。如此下去，當(dāng)T中的連通分量個(gè)數(shù)為1時(shí)，T中的該連通分量即為帶權(quán)圖G的一棵最小生成樹。2、克魯斯卡爾算法示例:,1,2,,4,3,5,6,,,,,,,,,,6,1,6

13、,5,5,5,6,3,4,2,最小代價(jià)生成樹,1,2,,4,3,5,6,,,,,1,5,3,4,2,,,5,5,,,,,,,,Kruskal算法是歸并邊，適用于稀疏圖,13,,例：利用克魯斯卡爾算法構(gòu)造最小生成樹的過(guò)程,14,8.6 最短路徑,典型用途：交通問題。如：城市A到城市B有多條線路，但每條線路的交通費(fèi)（或所需時(shí)間）不同，那么，如何選擇一條線路，使總費(fèi)用（或總時(shí)間）最少？問題抽象：在帶權(quán)有向圖中A點(diǎn)（源點(diǎn)）到達(dá)B點(diǎn)（終點(diǎn)）的多

14、條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。（注：最短路徑與最小生成樹不同，路徑上不一定包含n個(gè)頂點(diǎn)）,兩種常見的最短路徑問題：一、 單源最短路徑—用Dijkstra（迪杰斯特拉）算法二、所有頂點(diǎn)間的最短路徑—用Floyd（弗洛伊德）算法,一頂點(diǎn)到其余各頂點(diǎn),任意兩頂點(diǎn)之間,15,一、最短路徑的基本概念,1、圖的最短路徑和最短路徑長(zhǎng)度 圖中從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)可能存在多條路徑，路徑長(zhǎng)度最短的那條路徑稱作最短

15、路徑。其長(zhǎng)度稱作最短路徑長(zhǎng)度。2、帶權(quán)圖的最短路徑和最短路徑長(zhǎng)度 帶權(quán)圖中從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)可能存在多條路徑，帶權(quán)路徑長(zhǎng)度最短的那條路徑稱作最短路徑。其帶權(quán)路徑長(zhǎng)度稱作最短路徑長(zhǎng)度。,二、從一個(gè)結(jié)點(diǎn)（某個(gè)源點(diǎn)）到其余各頂點(diǎn)的最短路徑（單源最短路徑問題）,16,1、狄克斯特拉(Dijkstra) 算法思想,設(shè)置兩個(gè)結(jié)點(diǎn)的集合S和T，集合S中存放已找到最短路徑的結(jié)點(diǎn)，集合T中存放當(dāng)前還未找到最短路徑的結(jié)點(diǎn)。初始狀態(tài)時(shí)，集合

16、S中只包含源點(diǎn)，設(shè)為v0，然后不斷從集合T中選擇到源點(diǎn)v0路徑長(zhǎng)度最短的結(jié)點(diǎn)u加入到集合S中，集合S中每加入一個(gè)新的結(jié)點(diǎn)u都要修改從源點(diǎn)v0到集合T中剩余結(jié)點(diǎn)的當(dāng)前最短路徑長(zhǎng)度值，集合T中各結(jié)點(diǎn)的新的當(dāng)前最短路徑長(zhǎng)度值，為原來(lái)的最短路徑長(zhǎng)度值與從源點(diǎn)過(guò)結(jié)點(diǎn)u到達(dá)該結(jié)點(diǎn)的路徑長(zhǎng)度中的較小者。此過(guò)程不斷重復(fù)，直到集合T中的結(jié)點(diǎn)全部加入到集合S中為止。,,例：利用狄克斯特拉算法求如下所示圖中從頂點(diǎn)A到其余各頂點(diǎn)的最短路徑的過(guò)程。,17,,18

17、,1、采用狄克斯特拉算法實(shí)現(xiàn) 算法思想：每次以不同的結(jié)點(diǎn)作為源點(diǎn)，調(diào)用狄克斯特拉算法求出從該源點(diǎn)到其余結(jié)點(diǎn)的最短路徑。需重復(fù)調(diào)用n次狄克斯特拉算法。2、采用弗洛伊德算法，其算法思想如下：,二、每一對(duì)頂點(diǎn)之間的最短路徑,可以用如下遞推公式描述： A0[i][j]=cost[i][j] Ak+1[i][j]=min{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]}(0≤k≤n-1) 其中，cost

18、[i][j]中存放著序號(hào)為i的結(jié)點(diǎn)到序號(hào)為j的結(jié)點(diǎn)之間的權(quán)值 ； Ak[i][j](0≤k≤n-1) 表示從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序號(hào)不大于k的最短路徑長(zhǎng)度。,19,圖,,存儲(chǔ)結(jié)構(gòu),遍 歷,,鄰接矩陣,鄰 接 表,十字鏈表,鄰接多重表,,深度優(yōu)先搜索,廣度優(yōu)先搜索,,無(wú)向圖的應(yīng)用,,圖的連通分量,圖的生成樹,,最小生成樹,,Prim算法,Kruskal算法,,,Dijkstra算法,Floyd算法,（利用DFS）