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

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

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

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

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

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

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

7、定義，n 個頂點的連通網(wǎng)絡的生成樹肯定有 n 個頂點和僅僅n-1 條邊。,即有權圖,構造最小生成樹的準則必須只使用該網(wǎng)絡中的邊來構造最小生成樹；必須使用且僅使用n-1條邊來聯(lián)結網(wǎng)絡中的n個頂點；不能使用產(chǎn)生回路的邊。,目標：在網(wǎng)絡的多個生成樹中，尋找一個各邊權值之和最小的生成樹。,8,欲在n個城市間建立通信網(wǎng)，則n個城市應鋪n-1條線路；但因為每條線路都會有對應的經(jīng)濟成本，而n個城市可能有n(n-1)/2 條線路，那么，如何選擇

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

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

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

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

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

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

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

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

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

17、,1、采用狄克斯特拉算法實現(xiàn) 算法思想：每次以不同的結點作為源點，調(diào)用狄克斯特拉算法求出從該源點到其余結點的最短路徑。需重復調(diào)用n次狄克斯特拉算法。2、采用弗洛伊德算法，其算法思想如下：,二、每一對頂點之間的最短路徑,可以用如下遞推公式描述： 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]中存放著序號為i的結點到序號為j的結點之間的權值 ； Ak[i][j](0≤k≤n-1) 表示從結點vi到結點vj的路徑上所經(jīng)過的結點序號不大于k的最短路徑長度。,19,圖,,存儲結構,遍 歷,,鄰接矩陣,鄰 接 表,十字鏈表,鄰接多重表,,深度優(yōu)先搜索,廣度優(yōu)先搜索,,無向圖的應用,,圖的連通分量,圖的生成樹,,最小生成樹,,Prim算法,Kruskal算法,,,Dijkstra算法,Floyd算法,（利用DFS）