DFS和BFS用來干什么

1、DFS和BFS用來干什么？,連通性 拓?fù)渑判?關(guān)鍵路徑,連通分量 (Connected component) 當(dāng)無向圖為非連通圖時, 從圖中某一頂點(diǎn)出發(fā), 利用DFS或BFS不可能遍歷到圖中的所有頂點(diǎn), 只能訪問到該頂點(diǎn)所在的極大連通子圖(連通分量)的所有頂點(diǎn)。 若從無向圖的每一個連通分量中的一個頂點(diǎn)出發(fā)進(jìn)行遍歷, 可求得無向圖的所有連通分量。,圖的連通性問題,求連通分量的算法需要對圖的每一個頂點(diǎn)進(jìn)行檢測：若已被訪問過，則該頂點(diǎn)一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點(diǎn)出發(fā)遍歷圖，可求得圖的另一個連通分量。 對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。,A

2、,C,D,E,I,B,F,O,G,H,J,N,M,L,K,非連通無向圖,A,H,K,C,D,E,I,B,F,O,G,J,N,M,L,非連通圖的連通分量,最小生成樹 ( Minimum Cost Spanning Tree ),使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹。 按照生成樹的定義，n 個頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹有 n 個頂點(diǎn)、n-1 條邊。 構(gòu)造最小生成樹的準(zhǔn)則 必須使用且僅使用該網(wǎng)絡(luò)中的n-1 條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的 n 個頂點(diǎn)； 不能使用產(chǎn)生回路的邊； 各邊上的權(quán)值的總和達(dá)到最小。,MST 性質(zhì),假設(shè)N=(V,E）是一個連通網(wǎng),U是頂點(diǎn)集V的一

3、個非空子集。若(u,v)是一條具有最小權(quán)值（代價）的邊，其中uU,v V-U,則必存在一棵包含邊(u,v)的最小生成樹。,u,v,V- U,U,u,v,普里姆(Prim)算法,普里姆算法的基本思想： 從連通網(wǎng)絡(luò) N = ( V, E )中的某一頂點(diǎn) u0 出發(fā), U=u0。選擇與u0關(guān)聯(lián)的具有最小權(quán)值的邊 ( u0, v0 ), 將其頂點(diǎn)v0加入到生成樹頂點(diǎn)集合U中。 以后每一步從一個頂點(diǎn)在 U 中,而另一個頂點(diǎn)不在 U 中的各條邊中選擇權(quán)值最小的邊(u, v), 把頂點(diǎn)加入v到集合 U 中。如此繼續(xù)下去, 直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合 U 中為止。 采用鄰接矩陣作為圖的存儲表示

4、。,原圖 (a) (b),(c) (d) (e) (f),22,22,在構(gòu)造過程中，設(shè)置一個輔助數(shù)組： closedge0.vexnum-1 : 記錄從U到V-U具有最小代價的邊； 對每個頂點(diǎn)vi V-U : closedge i-1 .lowcost=Mincost(u, vi)|u U, closedgei-1.adjvex: 對應(yīng)這條邊依附的U中的頂點(diǎn)； 例子,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,void MiniSpanTree_PRIM ( MGraph G, VertexType u ) struct VertexType adjvex

5、; VRType lowcost; closedgeMAX_VERTEX_NUM; k=LocateVex(G,u); for (j=0;jG.vexnum;+j) if (j !=k) closedgej=u,G.arcskj.adj; closedgek.lowcost =0; /初始，U=u for (i=1;iG.vexnum;+) /選擇其余G.vexnum-1個頂點(diǎn) k=minimum(closedge); /求出T的下個頂點(diǎn):第k頂點(diǎn) printf(closedgek.adjvex,G.vexsk); closedgek.lowcost = 0; /第k頂點(diǎn)并入U集 for (

6、j=0;jG.vexnum;+j) /調(diào)整 if (G.arcskj.adj closedgej.lowcost) closedge j = G.vexk,G.arcskj.adj; 算法 7.9,Prim 算法,分析以上算法, 設(shè)連通網(wǎng)絡(luò)有 n 個頂點(diǎn), 則該算法的時間復(fù)雜度為 O(n2), 它適用于稠密網(wǎng)。 注意：當(dāng)各邊有相同權(quán)值時，由于選擇的隨意性，產(chǎn)生的生成樹可能不唯一。當(dāng)各邊的權(quán)值不相同時，產(chǎn)生的生成樹是唯一的。,克魯斯卡爾(Kruskal)算法,算法思想：從n個孤立頂點(diǎn)出發(fā)，順次加入n-1條邊。 假設(shè)連通網(wǎng)N=(V,E),令最小生成樹的初始狀態(tài)為只有n個頂點(diǎn)而無邊的非連通圖T=(V

7、,),圖中每個頂點(diǎn)自成一個連通分量。 在E中選擇代價最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入，否則舍去該邊而選擇下一條代價最小的邊。 依次類推，直至T中所有頂點(diǎn)都在同一連通分量上為止。 算法時間復(fù)雜度 O(eloge),適用于稀疏網(wǎng)。,有向無環(huán)圖(DAG)及其應(yīng)用,定義：一個無環(huán)的有向圖稱為有向無環(huán)圖。 有向無環(huán)圖是描述含有公共子式的表達(dá)式以及一項工程或系統(tǒng)進(jìn)行過程的有效工具。 用頂點(diǎn)表示活動的網(wǎng)絡(luò) (AOV網(wǎng)絡(luò)) 計劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。 例如

8、，計算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個工程，每一門課程的學(xué)習(xí)就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。,C1 高等數(shù)學(xué) C2 程序設(shè)計基礎(chǔ) C3 離散數(shù)學(xué) C1, C2 C4 數(shù)據(jù)結(jié)構(gòu) C3, C2 C5 高級語言程序設(shè)計 C2 C6 編譯方法 C5, C4 C7 操作系統(tǒng) C4, C9 C8 普通物理 C1 C9 計算機(jī)原理 C8,課程代號 課程名稱 先修課程,學(xué)生課程學(xué)習(xí)工程圖,可以用有向圖表示一個工程。在這種有向圖中，用頂點(diǎn)表示活動，用有向邊表示活動Vi 必須先于活動Vj 進(jìn)行。這種有向圖叫做頂點(diǎn)表示活動的AOV網(wǎng)絡(luò) (

9、Activity On Vertices)。 在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路, 即有向環(huán)。如果出現(xiàn)了有向環(huán)，則意味著某項活動應(yīng)以自己作為先決條件。 因此，對給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。,檢測有向環(huán)的一種方法是對AOV網(wǎng)絡(luò)構(gòu)造它的拓?fù)溆行蛐蛄小＜磳⒏鱾€頂點(diǎn) (代表各個活動)排列成一個線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。 這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算就叫做拓?fù)渑判颉?如果通過拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂點(diǎn)都排入一個拓?fù)溆行虻男蛄兄? 則該網(wǎng)絡(luò)中必定不會出現(xiàn)有向環(huán)。,如果AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行

10、的。 例如, 對學(xué)生選課工程圖進(jìn)行拓?fù)渑判? 得到的拓?fù)溆行蛐蛄袨?C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6,拓?fù)渑判虻姆椒? 輸入AOV網(wǎng)絡(luò)。令 n 為頂點(diǎn)個數(shù)。 在AOV網(wǎng)絡(luò)中選一個沒有直接前驅(qū)的頂點(diǎn), 并輸出之; 從圖中刪去該頂點(diǎn), 同時刪去所有它發(fā)出的有向邊; 重復(fù)以上 、步, 直到 全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬桑負(fù)渑判蛲瓿?；?圖中還有未輸出的頂點(diǎn), 但已跳出處理循環(huán)。說明圖中還剩下一些頂點(diǎn), 它們都有直接前驅(qū)。這時網(wǎng)絡(luò)中必存在有向環(huán)。,拓?fù)渑判?/p>

11、的過程,最后得到的拓?fù)溆行蛐蛄袨?C4 , C0 , C3 , C2 , C1 , C5 。它滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對于本來沒有這種關(guān)系的頂點(diǎn)，如C4和C2，也排出了先后次序關(guān)系。(即,得到了頂點(diǎn)集的一個全序關(guān)系）,(h) 拓?fù)渑判蛲瓿?AOV網(wǎng)絡(luò)及其鄰接表表示,C0,C1,C2,C3,C4,C5,C0 C1 C2 C3 C4 C5 ,0 1 2 3 4 5,indegree data adj,1 3 0 1 0 3,1,dest link,3 0,5,1,5 0,0,1,5 0,在鄰接表中增設(shè)一個數(shù)組indegree ，記錄各頂點(diǎn)入度。入度為零的頂點(diǎn)即無前驅(qū)頂點(diǎn)。 在輸入數(shù)據(jù)前,

12、 頂點(diǎn)表VexList 和入度數(shù)組indegree 全部初始化。在輸入數(shù)據(jù)時, 每輸入一條邊, 就需要建立一個邊結(jié)點(diǎn), 并將它鏈入相應(yīng)邊鏈表中, 統(tǒng)計入度信息： EdgeNode * p = new EdgeNode; p-dest = k; /建立邊結(jié)點(diǎn) p-link = G.VexListj.firstAdj; VexListj.firstAdj = p; /鏈入頂點(diǎn) j 的邊鏈表的前端 indegreek+; /頂點(diǎn) k 入度加一,在算法中, 使用一個存放入度為零的頂點(diǎn)的鏈?zhǔn)綏? 供選擇和輸出無前驅(qū)的頂點(diǎn)。 拓?fù)渑判蛩惴擅枋鋈缦拢?建立入度為零的頂點(diǎn)棧; 當(dāng)入度為零的頂點(diǎn)棧不空時, 重

13、復(fù)執(zhí)行 從頂點(diǎn)棧中退出一個頂點(diǎn), 并輸出之; 從AOV網(wǎng)絡(luò)中刪去這個頂點(diǎn)和它發(fā)出的邊, 邊的終頂點(diǎn)入度減一; 如果邊的終頂點(diǎn)入度減至0, 則該頂點(diǎn)進(jìn)入度為零的頂點(diǎn)棧; 如果輸出頂點(diǎn)個數(shù)少于AOV網(wǎng)絡(luò)的頂點(diǎn)個數(shù), 則報告網(wǎng)絡(luò)中存在有向環(huán)。,最短路徑 (Shortest Path),最短路徑問題：如果從圖中某一頂點(diǎn)(稱為源點(diǎn))到達(dá)另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小？ 問題解法: 邊上權(quán)值非負(fù)情形的單源最短路徑問題 Dijkstra算法 邊上權(quán)值為任意值的單源最短路徑問題 Bellman和Ford算法 所有頂點(diǎn)之間的最短路徑 Floyd算法

14、,邊上權(quán)值非負(fù)情形的單源最短路徑問題,問題的提法： 給定一個帶權(quán)有向圖D與源點(diǎn) v，求從 v 到D中其它頂點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。 為求得這些最短路徑, Dijkstra提出按路徑長度的遞增次序, 逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點(diǎn)v到其它各頂點(diǎn)的最短路徑全部求出為止。 舉例說明,Dijkstra逐步求解的過程,1,0,4,3,2,10,100,30,50,20,60,10,源點(diǎn) 終點(diǎn) 最短路徑 路徑長度,v0 v1 (v0,v1) 10 v2 (v0,v3,v2) 50 v3 (v0,v3) 3

15、0 v4 (v0,v3,v2 ,v4) 60,v,V-S,S:已求得的最短路徑的終點(diǎn)集,vj,vk,下一條最短路徑（設(shè)其終點(diǎn)為vj),或者是弧(v, vj),或者是從v出發(fā)，中間只經(jīng)過 S 中的頂點(diǎn)而最后到達(dá)vj的路徑。,調(diào)整： 每確定一個次短最短路徑終點(diǎn)Vj ， 1.將其并入S集; 2.調(diào)整V-S中其余頂點(diǎn)vk的“當(dāng)前找到的從源點(diǎn) v到終點(diǎn) vk 的最短路徑的長度Dk”: Dk Min Dk, Dj + arcsjk ,引入輔助向量D。它的每一個分量Di表示當(dāng)前找到的從源點(diǎn) v到終點(diǎn) vi 的最短路徑的長度。初始狀態(tài)： 若從源點(diǎn)v到頂點(diǎn) vi 有弧, 則Di為該邊上的權(quán)值； 若從源點(diǎn)v到頂點(diǎn)

16、 vi 無弧, 則Di為 。 假設(shè) S 是已求得的最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑（設(shè)其終點(diǎn)為x)或者是弧(v,x),或者是從v 出發(fā)，中間只經(jīng)過 S 中的頂點(diǎn)而最后到達(dá)x的路徑。 每次求得一條最短路徑后, 其終點(diǎn)vj 加入集合S，然后對所有的vk V-S，修改其 Di值。,Dijkstra算法, 初始化： S v; Di arcsLocateVex(G,v)i 選擇vj, 使得： Dj Min Di , vi V- S ; S S U j ; 修改： Dk Min Dk, Dj + arcsjk , 對于每一個 vk V- S ; 判斷：若 S = V, 則算法結(jié)束，否則轉(zhuǎn) 。,void ShortestPath_DIJ (MGraph G, int v0,PathMatrix ,/開始主循環(huán)每次求得v0到某個v頂點(diǎn)的最短路徑，并加v到S集。 for (i=1;iG.vexnum;+i) /其余G.vexnum-1個頂點(diǎn)