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

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

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

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

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

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

6、義為-1）。 int nextadj(G,v,w); 返回頂點v的鄰接點中處于鄰接點w之后的鄰接點號。 若不存在時，返回0（或定義為-1,13,8.2 圖的存儲,圖的存儲 圖結(jié)構(gòu)在計算機中的存儲形式 1. 鄰接矩陣 （1）不帶權(quán)值 假設(shè)圖中有n個頂點。則采用nn的矩陣A來表示， 1 E 其中 Aij 0 否則 例,0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0,行的方向：發(fā)出的弧 列的方向 ：進入的弧,14,8.2 圖的存儲,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,無向圖的鄰接矩陣 對稱,15,8.2 圖的存儲,2. 鄰接表表示法 將鄰接點構(gòu)成鏈表 例,data,firstadj,16,8.2 圖的存儲,逆鄰接鏈表 將“鄰接自”的頂點連成鏈表,data firstadj,data firstadj,代表弧,17,8.3 圖的遍歷,圖的遍歷訪問圖中所有頂點一次且僅且一次。 深度優(yōu)先搜索遍歷 圖的兩種遍歷算法 廣度優(yōu)先搜索遍歷 8.3.1 深度優(yōu)先搜索遍歷（Depth First Search) 這一問題求解包括幾個部分。 1. 基本算法 從頂點v0出發(fā)深度優(yōu)先搜索遍歷圖G的dfs (v0)描述如下： (1) 訪問v0； (2) 依次從v0的未被訪

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

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

10、值） 求鄰接點可以采用兩個函數(shù)： firstadj(G,v) ：返回v的第一個鄰接點（號），或0（不存在時）。 nextadj(G,v,w);返回v的第鄰接點中處于鄰接點w之后的鄰接點號, 或0（不存在時,訪問v0時， 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è)置標志數(shù)組visited的初值？ 能否在dfs算法中設(shè)置？ （3）從某頂點出發(fā)是否能保證訪問到所有頂點？ 或者說：選擇一個起點調(diào)用一次dfs算法，能否實現(xiàn)對整個圖的遍歷？ 2. 遍歷整個圖的算法 dfs算法在應(yīng)用于非連通圖，或者是某些有向圖時， 某一次調(diào)用就不能保證訪問到所有頂點。如下圖所示,23,8.3.1 深度優(yōu)先搜索遍歷,為此，需要重新選

12、擇起點來調(diào)用dfs算法。 如何選擇新的起點？ 起點應(yīng)滿足什么條件？ 將對訪問標志數(shù)組的賦初值運算， 以及選擇起點的控制合在一起， 構(gòu)成對整個圖的遍歷算法如下： 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è)計算法以判斷給定的無向圖是否是連通的？ （2）如何設(shè)計算法以求解給定的無向圖中的邊數(shù)？ （3）設(shè)計算法以判斷給定的無向圖是樹。 （4）設(shè)計算法以判斷給定的有

13、向圖是以v0為根的有向樹。 （5）設(shè)計算法以判斷圖中的一個節(jié)點是否為關(guān)節(jié)點,25,8.3.1 深度優(yōu)先搜索遍歷,例1 設(shè)計算法以求解無向圖G的連通分量的個數(shù)。 分析：對無向圖G來說，選擇某一頂點v執(zhí)行dfs(v)， 可訪問到所在連通分量中的所有頂點 因此，選擇起點的次數(shù)就是圖G的連通分量數(shù)， 這可通過修改遍歷整個圖的算法dfs_travel來實現(xiàn)：每調(diào)用一次dfs算法計數(shù)一次。 另外，考慮到要求求解連通分量數(shù)， 因而可以將算法設(shè)計為整型函數(shù)。 具體算法如下,26,8.3.1 深度優(yōu)先搜索遍歷,int numofGC(graph G) int i; int k=0; / k用于連通分量的計數(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來累計連通分量個數(shù) return k ;,遍歷整個圖的算法dfs_travel中的原來的部分,27,8.3.1 深度優(yōu)先搜索遍歷,例2 設(shè)計算法求出無向圖G的邊數(shù)。 算法如下： void dfs (graph G, int v ) int w; visitedv=TRUE; /設(shè)置訪問標志（訪問結(jié)點的其它操作被省去） w=firstadj(G,v); while (w!=0) E+; /此處意味著找到一條邊，故累計到

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記錄整個圖中的邊數(shù) for (i=1; i=n; i+) visitedi=FALSE; for (i=1; i=n; i+) if (visitedi=FALSE;) dfs(G,i); return E/2;,遍歷整個圖的算法dfs_travel中的原來的部分,29,8.3.1 深度優(yōu)先搜索遍歷,4. 深度遍歷算法的應(yīng)用二 例3：設(shè)計算法，將1-n(=

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

17、 （3）需要判斷首尾相接,31,8.3.1 深度優(yōu)先搜索遍歷,算法構(gòu)思如下: (1)設(shè)環(huán)上已有k個元素（0kn）。 (2)若kn, 且不在當前路徑上的頂點中存在與Bk相鄰的， 則依次從余下的頂點中取出與Bk相鄰的頂點放置在Bk+1中, 轉(zhuǎn)(1)。 (3)若kn，而在余下的這些頂點中找不到一個與BK相鄰的頂點， 或者是雖然存在鄰接點，但這些結(jié)點均已在同等條件下放置過了，因而須從環(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)。為避免遺漏某種放置，從最后往前依次用余下的頂點中的與其前面相鄰接的頂點替換,32,8.3.1 深度優(yōu)先搜索遍歷,采用遞歸方式實現(xiàn)如下： 其中visited為標志數(shù)組，表示各結(jié)點是否在當前的路徑上。 void getcc(int k) / A,B,visited為全局變量，k初值為1，B1固定為1 int i; if (k=n / 取消頂點i的放置，以便可被重新放入 調(diào)用前，要產(chǎn)生鄰接矩陣 A的值。數(shù)組visited全置為FALSE, visited1置為TRUE。k為1,B1為1。本遞歸算法利用函數(shù)調(diào)用及返回實現(xiàn)搜索與回溯，若不用遞歸，本算法則較為麻煩。試模擬執(zhí)行之,3

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

20、標志數(shù)組； (2)為了能依次訪問上一層次的訪問序列中的各頂點的鄰接點， 需要設(shè)置一個結(jié)構(gòu)以保存上一層次的頂點， 這一結(jié)構(gòu)還要滿足這樣的要求： 這一層中最先被訪問的頂點，其后繼也應(yīng)被最先檢測到。 由此可知，這一結(jié)構(gòu)應(yīng)是隊列。 (3)既然涉及到隊列（不妨Q），則需要安排隊列的運算： (a) 初始化； (b) 入隊：每訪問一個頂點v，除了訪問操作、設(shè)置標志外，還要將其入隊。 (c) 出隊：從隊列中刪除一個頂點v，這意味著要依次訪問v的所有未被訪問過的鄰接點,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. 遍歷整個圖的算法 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 最小生成樹,問題：修建一個連接各個小區(qū)與煤氣供應(yīng)站點之間的管道，使得造價成本最低，即構(gòu)造一顆最小生成樹。但是如何求解？ 對應(yīng)模型：樹結(jié)構(gòu)，生成樹，最小生成樹 8.4.1 prim算法 1. 基本思想 在滿足如下條件的邊中選出一條最小的邊： 一端已選，另一端未選。 因此，該算法需要給出起點，以作為已選頂點。 2. 實例 對右圖所示圖， 用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算法的簡要描述（設(shè)起點為v0）： 設(shè)置各候選邊(v0,vi)； for (i=1; i=n-1; i+) 從候選邊中找出權(quán)值最小的邊(v,vk)； /其中v已選邊，vk未選 將vk設(shè)置為已選頂點； 調(diào)整候選邊集合-調(diào)整新入選頂點和未選頂點之間的邊的集

24、合 由此可知，需要考慮如下幾個方面的實現(xiàn)： （1）已選頂點的標識：可用數(shù)組來或集合來存儲（或形式化描述）。 （2）候選邊的存儲 ： 雖然每個頂點可能對應(yīng)多個候選邊，但只要最小的一個， 因此，用一個數(shù)組也可以，不妨用edges（下標用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算法的時間復(fù)雜度,43,8.4 最小生成樹,void prim(graph G,gra

25、ph,初始化候選邊數(shù)組edges,初始化已選邊數(shù)組selected,prim算法的時間復(fù)雜度是O(n2,設(shè)置起始點已選,從候選邊中找出權(quán)值最小的邊,將k設(shè)置為已選頂點,調(diào)整候選邊集合,44,8.4 最小生成樹,2. 實例 判斷構(gòu)成回路的經(jīng)典方法：電位法： 初始狀態(tài)：各頂點的電位=頂點號 每當選擇一條邊時，相連通的頂點的電位全都按照其中最小的值設(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算法實現(xiàn)的討論

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

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

28、序列中，頂點vi領(lǐng)先于頂點vj。 滿足上述條件的頂點序列稱為拓撲序列， 產(chǎn)生這一序列的過程稱為拓撲排序。 由拓撲排序如何判斷是否存在有向回路？ 結(jié)論：如果能產(chǎn)生拓撲序列， 則說明AOV網(wǎng)中無回路，否則有回路,49,8.5.1 拓撲排序,拓撲排序算法簡單描述： 找一個入度為0的頂點v輸出； 刪除v及相關(guān)??； 重復(fù)，直到無入度為0的頂點為止。 此時，若所有頂點被輸出，則無回路， 否則有回路,50,8.5.1 拓撲排序?qū)嵗?1,6,6,6,6,對下圖所示AOV網(wǎng)進行拓撲排序,51,8.5.1 拓撲排序,判斷有無回路的條件：是否有拓撲序列。 思考： 入度數(shù)組Ind （數(shù)組初始化的實現(xiàn)）； “刪除v”的

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

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

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

33、點事件的最早發(fā)生時間。源點對應(yīng)事件的最早發(fā)生時間為0,3,4,5,9,8,14,13,12,19,0,59,8.5.2 關(guān)鍵路徑,程序?qū)崿F(xiàn)討論： 可在拓撲排序算法的基礎(chǔ)上添加操作來實現(xiàn)： 每當找到一個后繼頂點w，計算Ew，計算公式如下： Ew=maxEw, Ev+dutv,w 對應(yīng)語句： if (Ev+durv,wEw) Ew=Ev+dutv,w; 還要注意的問題： 各頂點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)鍵路徑,各頂點事件最遲發(fā)生時間的求解 為不耽誤工期，則需要求出各頂點對應(yīng)事件的最遲發(fā)生時間L . 每個頂點事件的最遲發(fā)生時間取決于其后繼頂點事件的最遲發(fā)生時間,61,8.5.2 關(guān)鍵路徑,最遲發(fā)生時間的求解,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)討論： 可在拓撲排序算法的基礎(chǔ)上添加操作來實現(xiàn)： 每當找到一個前驅(qū)頂點w，計算Lw, 計算公式如下： Lw=minLw, Lv-dutw,v 對應(yīng)語句： if (Lv-dutw,vLw) Lw= Lv-dutw,v; 還要注意的問題： 各頂點Li值得初始化。 算法與拓撲排序的關(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ā)生時間和最晚發(fā)生時間相等； 關(guān)鍵路徑上的活動的開始和結(jié)束事件發(fā)生的時間差等于活動的持續(xù)時間,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)鍵活動：a1，a4，a8，a9，a13

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