數(shù)據(jù)結(jié)構(gòu)第八章圖ppt課件

1、1,數(shù) 據(jù) 結(jié) 構(gòu) （第八章 圖） Data Structures 胡學(xué)鋼 張 晶 計(jì)算機(jī)與信息學(xué)院 2009年2月,2,第八章 圖 (Graph,第八章 圖（Graph) 8.1 基本概念和運(yùn)算 8.2 圖的存儲(chǔ) 8.3 圖的遍歷 8.4 最小生成樹 8.5 有向無環(huán)圖的應(yīng)用 8.6 最短路徑,3,8.1 基本概念和運(yùn)算,圖 由頂點(diǎn)集V和連接頂點(diǎn)的弧集E所組成的結(jié)構(gòu)， 記作 G = ( V, E )。 其中弧的形式為， 表示從頂點(diǎn)Vi到Vj之間有一條弧，圖形表示為： Vi Vj 有向圖 例：如右圖中的G1就是一個(gè)有向圖： 其中： 頂點(diǎn)集合 V=1，2，3，4 弧集 E= , , , ,4,8

2、.1 基本概念和運(yùn)算,如果頂點(diǎn)間的關(guān)系是相互的， 即弧的兩端沒有方向，則圖為無向圖。 其中的弧稱為邊。 邊的形式為(Vi,Vj)， 圖形表示為： Vi Vj 例：如右圖中的G2就是一個(gè)無向圖： 其中： 頂點(diǎn)集合 V=1，2，3，4 邊集 E= （1,2）,（1,3）,（1,4） （2,4）,（3,4）,5,8.1 基本概念和運(yùn)算,若G中每條邊（弧）對(duì)應(yīng)一個(gè)數(shù)值 表示關(guān)系的程度，則稱圖G為網(wǎng)絡(luò)。 例： 圖G3 就是一個(gè)網(wǎng)絡(luò) 對(duì)圖G = ( V, E )，若存在G1=(V1，E1)， 滿足V1V，E1E。則G1是G的子圖。 例如：右圖G4 就是G2 的子圖,6,8.1 基本概念和運(yùn)算,頂點(diǎn)間關(guān)系：

3、 如果 E 則稱 Vi，Vj相鄰接， Vi鄰接到Vj，Vj鄰接自Vi。 例如，右 圖中， V1鄰接到V2，V4鄰接自V3 若( Vi,Vj )E則稱Vi，Vj相鄰接 頂點(diǎn)的度 頂點(diǎn)的鄰接點(diǎn)的數(shù)目。 有向圖中：入度，出度。 度入度出度,7,8.1 基本概念和運(yùn)算,路徑 若 頂點(diǎn)序列Vi1，Vi2，Vik， 滿足E或 者(Vil，Vi(l+1)E）（l=1,2,k-1）， 則該頂點(diǎn)序列Vi1，Vi2，Vik 構(gòu)成一條路徑。 例: 圖G1中，1,2,4,1,3,4是一條路徑 簡(jiǎn)單路徑 中間經(jīng)過的頂點(diǎn)不重復(fù)的路徑。 例:圖G1中，( 1,2,4 ) ( 1,3,4 ) ( 1,3,4,1 ) 都是簡(jiǎn)單

4、路徑。 回路 首尾相同的路徑。 例如， ( 1,3,4,1 ) 簡(jiǎn)單回路 簡(jiǎn)單路徑 + 回路,8,8.1 基本概念和運(yùn)算,若無向圖中任意兩點(diǎn)間都存在路徑 則稱為連通圖。 否則，稱為不連通圖（非連通圖）。 非連通圖包含若干連通分量 極大連通子圖。 若有向圖中的任意兩點(diǎn)間可以互相到達(dá) 則稱為強(qiáng)連通圖,9,8.1 基本概念和運(yùn)算,若無向圖中任意兩點(diǎn)間都有一條邊 則稱為無向完全圖。 （共有n (n-1) / 2條邊） 若有向圖中每個(gè)頂點(diǎn)到其余各點(diǎn)均有一條弧 則稱為有向完全圖。 （共有n (n-1) 條邊,10,8.1 基本概念和運(yùn)算,若無向圖滿足：連通并且無回路 則稱為樹。 樹的定義有如下幾個(gè)等價(jià)的描

5、述： 有最少邊數(shù)的連通圖。 有n-1條邊的連通圖。 連通的無環(huán)圖。 有向樹 如果在有向圖中， 有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度為1， 則稱此圖為有向樹。 并稱其中入度為0的頂點(diǎn)為有向根。 右下圖就是一個(gè)有向樹，其中頂點(diǎn)1就是有向根,11,8.1 基本概念和運(yùn)算,圖的運(yùn)算： 基本運(yùn)算： 初始化圖 插入頂點(diǎn) 插入邊（?。?修改權(quán)值 刪除頂點(diǎn) 刪除邊（弧） 求指定頂點(diǎn)的鄰接點(diǎn) 常用運(yùn)算： 遍歷,12,8.1 基本概念和運(yùn)算,鄰接點(diǎn)的求解方法： 具體實(shí)現(xiàn)依賴于圖的存儲(chǔ)結(jié)構(gòu)， 可以考慮用兩個(gè)運(yùn)算來實(shí)現(xiàn)求解： int firstadj(G,v); 返回頂點(diǎn)v的第一個(gè)鄰接點(diǎn)號(hào)。 若不存在時(shí)，返回0（或定

6、義為-1）。 int nextadj(G,v,w); 返回頂點(diǎn)v的鄰接點(diǎn)中處于鄰接點(diǎn)w之后的鄰接點(diǎn)號(hào)。 若不存在時(shí)，返回0（或定義為-1,13,8.2 圖的存儲(chǔ),圖的存儲(chǔ) 圖結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式 1. 鄰接矩陣 （1）不帶權(quán)值 假設(shè)圖中有n個(gè)頂點(diǎn)。則采用nn的矩陣A來表示， 1 E 其中 Aij 0 否則 例,0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0,行的方向：發(fā)出的弧 列的方向 ：進(jìn)入的弧,14,8.2 圖的存儲(chǔ),2） 網(wǎng)絡(luò)的表示方法 wij E Aij 0 或 否則 例,4 3 5 4 2 3 6 5 2 6,0 1 1 1 1 0 0 1 1 0 0 1 1 1

7、 1 0,無向圖的鄰接矩陣 對(duì)稱,15,8.2 圖的存儲(chǔ),2. 鄰接表表示法 將鄰接點(diǎn)構(gòu)成鏈表 例,data,firstadj,16,8.2 圖的存儲(chǔ),逆鄰接鏈表 將“鄰接自”的頂點(diǎn)連成鏈表,data firstadj,data firstadj,代表弧,17,8.3 圖的遍歷,圖的遍歷訪問圖中所有頂點(diǎn)一次且僅且一次。 深度優(yōu)先搜索遍歷 圖的兩種遍歷算法 廣度優(yōu)先搜索遍歷 8.3.1 深度優(yōu)先搜索遍歷（Depth First Search) 這一問題求解包括幾個(gè)部分。 1. 基本算法 從頂點(diǎn)v0出發(fā)深度優(yōu)先搜索遍歷圖G的dfs (v0)描述如下： (1) 訪問v0； (2) 依次從v0的未被訪

8、問過的鄰接點(diǎn)出發(fā)深度遍歷,18,dfs(8,dfs(9,dfs(4,dfs(3,8.3.1 深度優(yōu)先搜索遍歷,下面以下圖為例來討論dfs算法的執(zhí)行過程：調(diào)用dfs(1,此箭頭表示是從遍歷運(yùn)算dfs(1)中調(diào)用dfs(2)，即從頂點(diǎn)1直接轉(zhuǎn)到2,此虛箭頭表示是在dfs(3)執(zhí)行完畢后返回到遍歷運(yùn)算dfs(2)中，即從頂點(diǎn)3返回到2,9,dfs(1,dfs(2,dfs(5,dfs(6,dfs(7,dfs(10,在訪問頂點(diǎn)3后，由于頂點(diǎn)3的鄰接點(diǎn)已全被訪問，故dfs（3）執(zhí)行到此結(jié)束，應(yīng)返回到調(diào)用層，即返回到dfs(2,dfs(1)包含如下兩部分操作： （1）訪問頂點(diǎn)1； （2）依次執(zhí)行dfs(2)

9、和dfs(8,19,8.3.1 深度優(yōu)先搜索遍歷,將dfs（1）執(zhí)行過程中所搜索的邊連接起來（有標(biāo)注的邊）， 得到一棵生成樹-dfs生成樹,原圖及其搜索示意圖,dfs(1)生成樹,20,8.3.1 深度優(yōu)先搜索遍歷,下面討論dfs算法的設(shè)計(jì)。 為此，先回顧一下dfs (v0)的描述： (1) 訪問v0； (2) 依次從v0的未被訪問過的鄰接點(diǎn)出發(fā)深度遍歷。 分析：由算法描述可知： 訪問頂點(diǎn)v0的基本操作： 可用visite(v0)簡(jiǎn)單表示。 設(shè)置訪問標(biāo)志數(shù)組visited ，并約定： 某頂點(diǎn)vi未被訪問時(shí)， visitedi=FALSE（初值） vi被訪問過后， visitedi=TRUE（初

10、值） 求鄰接點(diǎn)可以采用兩個(gè)函數(shù)： firstadj(G,v) ：返回v的第一個(gè)鄰接點(diǎn)（號(hào)），或0（不存在時(shí)）。 nextadj(G,v,w);返回v的第鄰接點(diǎn)中處于鄰接點(diǎn)w之后的鄰接點(diǎn)號(hào), 或0（不存在時(shí),訪問v0時(shí)， visitedi=TRUE,21,Y,N,8.3.1 深度優(yōu)先搜索遍歷,由討論可得到dfs算法的流程圖如下： 由此得深度遍歷基本算法dfs(v0)如下 : void dfs(int v0) visite(v0); visitedv0=TRUE; w=firstadj(G,v0); while(w!=0) if(!visitedw) dfs(w); w=nextadj(G,v0,

11、w);,N,visite(v0); visitedv0=TRUE,W=0,W被訪問過,dfs(w,w=nextadj(G,v,w,w=firstadj(G,v),22,8.3.1 深度優(yōu)先搜索遍歷,問題： （1）dfs算法是否適用于有向圖？ （2）如何設(shè)置標(biāo)志數(shù)組visited的初值？ 能否在dfs算法中設(shè)置？ （3）從某頂點(diǎn)出發(fā)是否能保證訪問到所有頂點(diǎn)？ 或者說：選擇一個(gè)起點(diǎn)調(diào)用一次dfs算法，能否實(shí)現(xiàn)對(duì)整個(gè)圖的遍歷？ 2. 遍歷整個(gè)圖的算法 dfs算法在應(yīng)用于非連通圖，或者是某些有向圖時(shí)， 某一次調(diào)用就不能保證訪問到所有頂點(diǎn)。如下圖所示,23,8.3.1 深度優(yōu)先搜索遍歷,為此，需要重新選

12、擇起點(diǎn)來調(diào)用dfs算法。 如何選擇新的起點(diǎn)？ 起點(diǎn)應(yīng)滿足什么條件？ 將對(duì)訪問標(biāo)志數(shù)組的賦初值運(yùn)算， 以及選擇起點(diǎn)的控制合在一起， 構(gòu)成對(duì)整個(gè)圖的遍歷算法如下： void travel_dfs(graph G) for (i=1; i=n; i+) visitedi=FALSE; for (i=1; i=n; i+) if(!visitedi) dfs(i);,24,8.3.1 深度優(yōu)先搜索遍歷,3. 深度遍歷算法的應(yīng)用 問題： （1）如何設(shè)計(jì)算法以判斷給定的無向圖是否是連通的？ （2）如何設(shè)計(jì)算法以求解給定的無向圖中的邊數(shù)？ （3）設(shè)計(jì)算法以判斷給定的無向圖是樹。 （4）設(shè)計(jì)算法以判斷給定的有

13、向圖是以v0為根的有向樹。 （5）設(shè)計(jì)算法以判斷圖中的一個(gè)節(jié)點(diǎn)是否為關(guān)節(jié)點(diǎn),25,8.3.1 深度優(yōu)先搜索遍歷,例1 設(shè)計(jì)算法以求解無向圖G的連通分量的個(gè)數(shù)。 分析：對(duì)無向圖G來說，選擇某一頂點(diǎn)v執(zhí)行dfs(v)， 可訪問到所在連通分量中的所有頂點(diǎn) 因此，選擇起點(diǎn)的次數(shù)就是圖G的連通分量數(shù)， 這可通過修改遍歷整個(gè)圖的算法dfs_travel來實(shí)現(xiàn)：每調(diào)用一次dfs算法計(jì)數(shù)一次。 另外，考慮到要求求解連通分量數(shù)， 因而可以將算法設(shè)計(jì)為整型函數(shù)。 具體算法如下,26,8.3.1 深度優(yōu)先搜索遍歷,int numofGC(graph G) int i; int k=0; / k用于連通分量的計(jì)數(shù) f

14、or (i=1; i=n; i+) visitedi=FALSE; for (i=1; i=n; i+) if (visitedi=FALSE) k+; dfs(G,i); /用k來累計(jì)連通分量個(gè)數(shù) return k ;,遍歷整個(gè)圖的算法dfs_travel中的原來的部分,27,8.3.1 深度優(yōu)先搜索遍歷,例2 設(shè)計(jì)算法求出無向圖G的邊數(shù)。 算法如下： void dfs (graph G, int v ) int w; visitedv=TRUE; /設(shè)置訪問標(biāo)志（訪問結(jié)點(diǎn)的其它操作被省去） w=firstadj(G,v); while (w!=0) E+; /此處意味著找到一條邊，故累計(jì)到

15、變量E中 if (visitedw=FALSE) dfs(G,w); w=nextadj(G,v,w);,dfs算法中原有的操作,28,8.3.1 深度優(yōu)先搜索遍歷,int Enum (graph G ) int i; E=0; /全局變量E記錄整個(gè)圖中的邊數(shù) for (i=1; i=n; i+) visitedi=FALSE; for (i=1; i=n; i+) if (visitedi=FALSE;) dfs(G,i); return E/2;,遍歷整個(gè)圖的算法dfs_travel中的原來的部分,29,8.3.1 深度優(yōu)先搜索遍歷,4. 深度遍歷算法的應(yīng)用二 例3：設(shè)計(jì)算法，將1-n(=

16、20,或其他數(shù))放在一個(gè)環(huán)上，使環(huán)上任意兩個(gè)相鄰元素的和為質(zhì)數(shù)。 分析：可以用圖來描述該問題： 用頂點(diǎn)表示一個(gè)數(shù) 若兩個(gè)數(shù)的和為質(zhì)數(shù)， 則對(duì)應(yīng)頂點(diǎn)之間有一條邊。 例如，若n=10，對(duì)應(yīng)圖如右所示。 在這一表示下，問題轉(zhuǎn)化為： 求圖中包含所有頂點(diǎn)的簡(jiǎn)單回路。 如圖所示的一個(gè)解。 （1，2，3，4，7，6，5，8，9，10,30,8.3.1 深度優(yōu)先搜索遍歷,算法設(shè)計(jì)中需要注意的： 通過在dfs算法的基礎(chǔ)上變化而得： （1）路徑的記錄：需要增加變量或參數(shù)以記錄路徑，因此，不妨設(shè)一個(gè)數(shù)組以記錄路徑中的頂點(diǎn)序列和一個(gè)記錄長度的變量。 （2）若某些走法行不通，需要重來，為此，要恢復(fù)visitedi標(biāo)志。

17、 （3）需要判斷首尾相接,31,8.3.1 深度優(yōu)先搜索遍歷,算法構(gòu)思如下: (1)設(shè)環(huán)上已有k個(gè)元素（0kn）。 (2)若kn, 且不在當(dāng)前路徑上的頂點(diǎn)中存在與Bk相鄰的， 則依次從余下的頂點(diǎn)中取出與Bk相鄰的頂點(diǎn)放置在Bk+1中, 轉(zhuǎn)(1)。 (3)若kn，而在余下的這些頂點(diǎn)中找不到一個(gè)與BK相鄰的頂點(diǎn)， 或者是雖然存在鄰接點(diǎn)，但這些結(jié)點(diǎn)均已在同等條件下放置過了，因而須從環(huán)上去掉BK，轉(zhuǎn)(1)。 (4)若k=,有兩種情況: (a)Bn與B1相鄰接, 說明已求得一解, 則輸出求解結(jié)果, 然后返回。 (b)Bn與B1不鄰接，說明前面的放置法不行, 即不構(gòu)成環(huán), 因而需要重新放置，即要去掉Bn和

18、Bn-1，然而轉(zhuǎn)(1)。為避免遺漏某種放置，從最后往前依次用余下的頂點(diǎn)中的與其前面相鄰接的頂點(diǎn)替換,32,8.3.1 深度優(yōu)先搜索遍歷,采用遞歸方式實(shí)現(xiàn)如下： 其中visited為標(biāo)志數(shù)組，表示各結(jié)點(diǎn)是否在當(dāng)前的路徑上。 void getcc(int k) / A,B,visited為全局變量，k初值為1，B1固定為1 int i; if (k=n / 取消頂點(diǎn)i的放置，以便可被重新放入 調(diào)用前，要產(chǎn)生鄰接矩陣 A的值。數(shù)組visited全置為FALSE, visited1置為TRUE。k為1,B1為1。本遞歸算法利用函數(shù)調(diào)用及返回實(shí)現(xiàn)搜索與回溯，若不用遞歸，本算法則較為麻煩。試模擬執(zhí)行之,3

19、3,8.3.2 廣度優(yōu)先搜索遍歷,8.3.2 廣度優(yōu)先搜索遍歷（Breadth_first search) 廣度優(yōu)先遍歷 由近及遠(yuǎn)逐層訪問頂點(diǎn)（典型的層次遍歷） 1. 基本算法 從頂點(diǎn)v0出發(fā)廣度優(yōu)先搜索遍歷圖的算法bfs(v0): （1）訪問v0 （2）依次訪問v0的各鄰接點(diǎn)。 （3）設(shè)最近一層訪問序列為vi1，vi2，vik， 則依次訪問 vi1，vi2，vik的 未被訪問過的鄰接點(diǎn),34,8.3.2 廣度優(yōu)先搜索遍歷,bfs(1)的執(zhí)行過程如下圖所示。 其中用紅線標(biāo)注搜索路線。 將搜索的便連起來得到bfs生成樹,bfs生成樹,35,8.3.2 廣度優(yōu)先搜索遍歷,算法構(gòu)思： (1) 設(shè)訪問

20、標(biāo)志數(shù)組； (2)為了能依次訪問上一層次的訪問序列中的各頂點(diǎn)的鄰接點(diǎn)， 需要設(shè)置一個(gè)結(jié)構(gòu)以保存上一層次的頂點(diǎn)， 這一結(jié)構(gòu)還要滿足這樣的要求： 這一層中最先被訪問的頂點(diǎn)，其后繼也應(yīng)被最先檢測(cè)到。 由此可知，這一結(jié)構(gòu)應(yīng)是隊(duì)列。 (3)既然涉及到隊(duì)列（不妨Q），則需要安排隊(duì)列的運(yùn)算： (a) 初始化； (b) 入隊(duì)：每訪問一個(gè)頂點(diǎn)v，除了訪問操作、設(shè)置標(biāo)志外，還要將其入隊(duì)。 (c) 出隊(duì)：從隊(duì)列中刪除一個(gè)頂點(diǎn)v，這意味著要依次訪問v的所有未被訪問過的鄰接點(diǎn),36,8.3.2 廣度優(yōu)先搜索遍歷,廣度遍歷的基本算法如下： void bfs(int v0) Queue Q; visite(v0); vis

21、itedv0=TRUE; Q.append(v0); while(!Q.Empty() v=Q.Serve(); w=firstadj(G,v); while(w!=0) if(!visitew) visite(w); visitedw=TRUE; Q.append(w); w=nextadj(G,v,w);,37,8.3.2 廣度優(yōu)先搜索遍歷,2. 遍歷整個(gè)圖的算法 void travel_bfs(graph G) for(i=1;i=n;i+) visitedi=FALSE; for(i=1;i=n;i+) if(!visitedi) bfs(i); 3.廣度遍歷算法的應(yīng)用 例：迷宮中的最

22、短路徑算法,38,8.4 最小生成樹,問題：修建一個(gè)連接各個(gè)小區(qū)與煤氣供應(yīng)站點(diǎn)之間的管道，使得造價(jià)成本最低，即構(gòu)造一顆最小生成樹。但是如何求解？ 對(duì)應(yīng)模型：樹結(jié)構(gòu)，生成樹，最小生成樹 8.4.1 prim算法 1. 基本思想 在滿足如下條件的邊中選出一條最小的邊： 一端已選，另一端未選。 因此，該算法需要給出起點(diǎn)，以作為已選頂點(diǎn)。 2. 實(shí)例 對(duì)右圖所示圖， 用Prim算法求最小生成樹,39,8.4 最小生成樹,40,8.4 最小生成樹-求解過程的表格化求解,1,1,6,1,6,5,1,6,5,4,1,6,5,4,3,1,6,5,4,3,2,1,2)/12,1,3),1,4),1,5)/9,1

23、,6)/9,1,2)/12 (6,2)/15,6,3)/17,6,4)/20,1,5)/9 (6,5)/9,6,4)/20 (5,4)/4,1,2)/12 (6,2)/15,6,3)/17,1,2)/12 (6,2)/15,6,3)/17 (4,3)/3,1,2)/12 (6,2)/15 (3,2)/6,41,8.4 最小生成樹,3.算法 Prim算法的簡(jiǎn)要描述（設(shè)起點(diǎn)為v0）： 設(shè)置各候選邊(v0,vi)； for (i=1; i=n-1; i+) 從候選邊中找出權(quán)值最小的邊(v,vk)； /其中v已選邊，vk未選 將vk設(shè)置為已選頂點(diǎn)； 調(diào)整候選邊集合-調(diào)整新入選頂點(diǎn)和未選頂點(diǎn)之間的邊的集

24、合 由此可知，需要考慮如下幾個(gè)方面的實(shí)現(xiàn)： （1）已選頂點(diǎn)的標(biāo)識(shí)：可用數(shù)組來或集合來存儲(chǔ)（或形式化描述）。 （2）候選邊的存儲(chǔ) ： 雖然每個(gè)頂點(diǎn)可能對(duì)應(yīng)多個(gè)候選邊，但只要最小的一個(gè)， 因此，用一個(gè)數(shù)組也可以，不妨用edges（下標(biāo)用1-n即可,42,8.4 最小生成樹,初始化候選邊數(shù)組edges； U=v0； for (i=1; i=n-1; i+) k=最小候選邊的未選的一端； U=U+k； 以k修改edges； 注：edges的元素可以設(shè)置為v 思考：權(quán)值最小的邊一定在最小生成樹中么？ 分析 : prim算法的時(shí)間復(fù)雜度,43,8.4 最小生成樹,void prim(graph G,gra

25、ph,初始化候選邊數(shù)組edges,初始化已選邊數(shù)組selected,prim算法的時(shí)間復(fù)雜度是O(n2,設(shè)置起始點(diǎn)已選,從候選邊中找出權(quán)值最小的邊,將k設(shè)置為已選頂點(diǎn),調(diào)整候選邊集合,44,8.4 最小生成樹,2. 實(shí)例 判斷構(gòu)成回路的經(jīng)典方法：電位法： 初始狀態(tài)：各頂點(diǎn)的電位=頂點(diǎn)號(hào) 每當(dāng)選擇一條邊時(shí)，相連通的頂點(diǎn)的電位全都按照其中最小的值設(shè)置。 由此可知新的候選邊是否和已選邊構(gòu)成回路 -判斷方法,Kruskal算法 1.基本思想 反復(fù)在滿足如下條件的邊中選出一條最小的邊 和已選邊不構(gòu)成回路,1,3,2,4,5,6,7,1,2,1,1,1,1,1,45,8.4 最小生成樹,3算法實(shí)現(xiàn)的討論

26、Kruskal算法的簡(jiǎn)要描述： T=(V,) ; /初始化生成樹T while(T中所含邊數(shù)n-1) 從E中選取當(dāng)前最短邊(u,v)； 從E中刪去邊(u,v)； if ( (u,v)與T中邊不構(gòu)成回路) 將邊(u,v)加入T中；,需解決問題： （1）候選邊的存儲(chǔ) （2）判斷所選擇的邊和已選的邊不構(gòu)成回路,分析 Kruskal算法的時(shí)間復(fù)雜度為(eloge)、(n3) 。 其時(shí)間性能和空間性能都不是很如意,46,8.4 最小生成樹Kruskal算法練習(xí),Kruskal算法 基本思想 反復(fù)在滿足如下條件的邊中選出一條最小的邊 使其和已選邊不構(gòu)成回路,Kruskal最小生成樹,47,8.5 有向無環(huán)

27、圖的應(yīng)用,工程由多項(xiàng)活動(dòng)構(gòu)成，且活動(dòng)之間存在一定制約。 工程問題： 1) 工程能否順利進(jìn)行？ 2) 工程至少需要的時(shí)間？ 3) 工程中哪些是關(guān)鍵環(huán)節(jié)？ 8.5.1 拓?fù)渑判?對(duì)第一類問題的求解： 用圖來表示工程：其中， 用頂點(diǎn)表示活動(dòng)；弧表示活動(dòng)之間的制約關(guān)系。 稱這種圖為AOV網(wǎng)(Activity On Vertex Network,工程是否順利進(jìn)行,AOV網(wǎng)是否存在有向回路,48,8.5.1 拓?fù)渑判?如何判斷AOV網(wǎng)中是否存在有向回路？ 解決方法： (1)用深度遍歷要做許多試探性工作； (2)用產(chǎn)生(包含所有) 頂點(diǎn)序列的方法，頂點(diǎn)序列滿足： 在圖中，若頂點(diǎn)vi到頂點(diǎn)vj存在路徑， 則在

28、序列中，頂點(diǎn)vi領(lǐng)先于頂點(diǎn)vj。 滿足上述條件的頂點(diǎn)序列稱為拓?fù)湫蛄校?產(chǎn)生這一序列的過程稱為拓?fù)渑判颉?由拓?fù)渑判蛉绾闻袛嗍欠翊嬖谟邢蚧芈罚?結(jié)論：如果能產(chǎn)生拓?fù)湫蛄校?則說明AOV網(wǎng)中無回路，否則有回路,49,8.5.1 拓?fù)渑判?拓?fù)渑判蛩惴ê?jiǎn)單描述： 找一個(gè)入度為0的頂點(diǎn)v輸出； 刪除v及相關(guān)弧； 重復(fù)，直到無入度為0的頂點(diǎn)為止。 此時(shí)，若所有頂點(diǎn)被輸出，則無回路， 否則有回路,50,8.5.1 拓?fù)渑判驅(qū)嵗?1,6,6,6,6,對(duì)下圖所示AOV網(wǎng)進(jìn)行拓?fù)渑判?51,8.5.1 拓?fù)渑判?判斷有無回路的條件：是否有拓?fù)湫蛄小?思考： 入度數(shù)組Ind （數(shù)組初始化的實(shí)現(xiàn)）； “刪除v”的

29、實(shí)現(xiàn)后繼的入度減一； 找入度為0的頂點(diǎn) 將入度為0的待輸出頂點(diǎn)放到棧中，若出現(xiàn)入度為0 的頂點(diǎn)則入棧。 拓?fù)渑判蛩惴ㄔO(shè)計(jì) 拓?fù)渑判蛩惴ǎ?初始化入度數(shù)組Ind （若出現(xiàn)0入度頂點(diǎn)，則入棧s）； 若棧s為空，則跳出循環(huán)，轉(zhuǎn)到 v=pop(s)并輸出v； 對(duì)v的所有后繼w實(shí)現(xiàn)：Indw-1；若Indw=0；則w入棧； 轉(zhuǎn)； 判斷是否存在回路,拓?fù)渑判蛩惴ê?jiǎn)單描述： 找一個(gè)入度為0的頂點(diǎn)v輸出； 刪除v及相關(guān)??； 重復(fù)，直到無入度為0的頂點(diǎn)為止。 此時(shí)，若所有頂點(diǎn)被輸出，則無回路， 否則有回路,52,8.5.1 拓?fù)渑判?棧的演示,1,2,3,5,4,6,0,0,1,1,1,0,0,0,53,8.5

30、 有向無環(huán)圖的應(yīng)用拓?fù)渑判?Bool toposort(graph G) get_Ind(G,Ind); stack s; int count=0; for(i=1;i=n;i+) if ( Indi = 0 ) s.push(i); while ( !s.empty() ) v=s.pop(); coutv; count+; w=firstadj(G,v); while(w!=0) Indw-; if ( Indw = 0 ) s.push(w); w=nextadj(G,v,w); if ( count = n ) return TURE: else returen FALSE;,分析 若

31、圖采用鄰接矩陣來存儲(chǔ)，則算法復(fù)雜度為(n2)； 若圖采用鄰接表來存儲(chǔ)，則算法復(fù)雜度為(n+e,54,8.5 有向無環(huán)圖的應(yīng)用練習(xí),例:寫出一個(gè)拓?fù)湫蛄?所以，其中一種拓?fù)湫蛄袨椋?2 5 1 4 7 3 6 8 9 10 思考：寫出所有的拓?fù)渑判?55,8.5.2 關(guān)鍵路徑,另一類工程問題： 工程至少需要的時(shí)間？ 工程中哪些是關(guān)鍵環(huán)節(jié)？ 為此，用圖來表示工程：其中， 用弧表示活動(dòng)；用弧的權(quán)值表示活動(dòng)的持續(xù)時(shí)間； 用弧兩端的頂點(diǎn)分別表示活動(dòng)的開始和結(jié)束，即瞬間行為或事件。 這種圖稱為AOE網(wǎng)(Activity On Edge Network,56,8.5.2 關(guān)鍵路徑,在AOE網(wǎng)中， 稱開始點(diǎn)為

32、源點(diǎn)， 稱結(jié)束點(diǎn)為匯點(diǎn)。 整個(gè)工程所需要的最少時(shí)間： 是從源點(diǎn)到匯點(diǎn)之間的最長的一條路徑-關(guān)鍵路徑(critical path)。 由此可知，問題變成求解 求解AOE網(wǎng)中的關(guān)鍵路徑,57,8.5.2 關(guān)鍵路徑,如何求解關(guān)鍵路徑？ 可分2個(gè)步驟來求解： （1）求解各頂點(diǎn)事件的最早發(fā)生時(shí)間 由此可得到匯點(diǎn)事件的最早發(fā)生時(shí)間 -整個(gè)工程最少需要的時(shí)間 （2）反推各頂點(diǎn)時(shí)間的最遲發(fā)生時(shí)間 由此可得到不能耽誤的活動(dòng)， 此類活動(dòng)連起來，構(gòu)成關(guān)鍵路徑,58,8.5.2 關(guān)鍵路徑,各頂點(diǎn)事件最早發(fā)生時(shí)間的求解： 為求最長路經(jīng)，則需求各頂點(diǎn)對(duì)應(yīng)事件的最早發(fā)生時(shí)間E ; 每個(gè)頂點(diǎn)事件的最早發(fā)生時(shí)間，依賴于其前驅(qū)頂

33、點(diǎn)事件的最早發(fā)生時(shí)間。源點(diǎn)對(duì)應(yīng)事件的最早發(fā)生時(shí)間為0,3,4,5,9,8,14,13,12,19,0,59,8.5.2 關(guān)鍵路徑,程序?qū)崿F(xiàn)討論： 可在拓?fù)渑判蛩惴ǖ幕A(chǔ)上添加操作來實(shí)現(xiàn)： 每當(dāng)找到一個(gè)后繼頂點(diǎn)w，計(jì)算Ew，計(jì)算公式如下： Ew=maxEw, Ev+dutv,w 對(duì)應(yīng)語句： if (Ev+durv,wEw) Ew=Ev+dutv,w; 還要注意的問題： 各頂點(diǎn)Ei值得初始化,Bool toposort(graph G) get_Ind(G,Ind); stack s; int count=0; for(i=1;i=n;i+) if ( Indi = 0 ) s.push(i);

34、while ( !s.empty() ) v=s.pop(); coutv; count+; w=firstadj(G,v); while(w!=0) Indw-; if ( Indw = 0 ) s.push(w); w=nextadj(G,v,w); if ( count = n ) return TURE: else returen FALSE;,60,8.5.2 關(guān)鍵路徑,各頂點(diǎn)事件最遲發(fā)生時(shí)間的求解 為不耽誤工期，則需要求出各頂點(diǎn)對(duì)應(yīng)事件的最遲發(fā)生時(shí)間L . 每個(gè)頂點(diǎn)事件的最遲發(fā)生時(shí)間取決于其后繼頂點(diǎn)事件的最遲發(fā)生時(shí)間,61,8.5.2 關(guān)鍵路徑,最遲發(fā)生時(shí)間的求解,1,2,3,4,

35、5,6,7,8,9,10,a1=3,a3=5,a2=4,a5=3,a4=6,a8=5,a9=4,a6=4,a10=3,a12=6,a11=4,a15=4,a14=6,a13=5,a7=3,3,4,5,9,8,14,13,12,19,19,15,13,14,9,10,7,6,3,0,0,62,8.5.2 關(guān)鍵路徑,程序?qū)崿F(xiàn)討論： 可在拓?fù)渑判蛩惴ǖ幕A(chǔ)上添加操作來實(shí)現(xiàn)： 每當(dāng)找到一個(gè)前驅(qū)頂點(diǎn)w，計(jì)算Lw, 計(jì)算公式如下： Lw=minLw, Lv-dutw,v 對(duì)應(yīng)語句： if (Lv-dutw,vLw) Lw= Lv-dutw,v; 還要注意的問題： 各頂點(diǎn)Li值得初始化。 算法與拓?fù)渑判虻年P(guān)

36、系,Bool toposort(graph G) get_Ind(G,Ind); stack s; int count=0; for(i=1;i=n;i+) if ( Indi = 0 ) s.push(i); while ( !s.empty() ) v=s.pop(); coutv; count+; w=firstadj(G,v); while(w!=0) Indw-; if ( Indw = 0 ) s.push(w); w=nextadj(G,v,w); if ( count = n ) return TURE: else returen FALSE;,63,8.5.2 關(guān)鍵路徑,如何

37、求解AOE網(wǎng)中的關(guān)鍵路徑？ 關(guān)鍵路徑上的事件最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間相等； 關(guān)鍵路徑上的活動(dòng)的開始和結(jié)束事件發(fā)生的時(shí)間差等于活動(dòng)的持續(xù)時(shí)間,64,8.5.2 關(guān)鍵路徑,關(guān)鍵路徑的求解方法及路徑,1,2,3,4,5,6,7,8,9,10,a1=3,a3=5,a2=4,a5=3,a4=6,a8=5,a9=4,a6=4,a10=3,a12=6,a11=4,a15=4,a14=6,a13=5,a7=3,3,4,5,9,8,14,13,12,19,19,15,13,14,9,10,7,6,3,0,0,關(guān)鍵路徑：（1,2,5,7,10）和（1,2,5,8,10） 關(guān)鍵活動(dòng)：a1，a4，a8，a9，a13

38、，a14,65,8.6 最短路徑(Shortest path,從單個(gè)點(diǎn)到其余各點(diǎn)之間的最短路徑 Dijkstra算法 各點(diǎn)之間的最短路徑 Floyd算法,66,8.6 最短路徑Dijkstra算法,從單個(gè)點(diǎn)到其余各點(diǎn)間的最短路徑Dijkstra算法 基本思想 按照最短路徑長度不減的次序求各頂點(diǎn)的解。 若已知道路v0v1v2v3vn-1vn是v0到vn最近的路， 則途經(jīng)的某頂點(diǎn)vi也為v0到vi最短的路,67,8.6 最短路徑Dijkstra算法描述,方法如下： （其中：pathv和distv表示從v0到v的最短路徑及其長度） （1）對(duì)v0以外的各頂點(diǎn)vi，若存在， 則將其作為v0到vi的（暫時(shí)的）最短路徑存放到pathv中， 將其權(quán)值作為對(duì)應(yīng)的路徑長度存放到distv中。 （2）從未解頂點(diǎn)中選擇一個(gè)dist值最小的頂點(diǎn)v， 則當(dāng)前的pathv和distv就是頂點(diǎn)v的最終解。 （3）由于某些頂點(diǎn)經(jīng)過v可能會(huì)使得從v0到該頂點(diǎn)的路徑更近 一些，因此，應(yīng)修改這些頂點(diǎn)的路徑及其長度的值。 （4）重復(fù)（2）（