1、 第五章 圖5.1 基本概念5.2 圖的存儲結構5.3 圖的遍歷5.4 拓撲排序5.5 關鍵路徑 5.6 最短路徑5.7 最小支撐樹5.8 圖的應用5.5.1 基本概念 邊表示活動(Activity) 邊的權值表示活動的持續時間(Duration) 頂點表示入邊的活動已完成，出邊的活動可以開始的狀態，也稱為事件(Event) 這樣的有向無環的帶權圖叫做AOE (Activity On Edges)網。例 某工程源點：表示整個工程的開始（入度為零）。匯點：表示整個工程的結束（出度為零）。完成整個工程至少需要多少時間？為縮短工程的時間，應當加快哪些活動？325140867a1=6a8=7a7=9a

2、6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點源點從源點到各頂點的路徑可能不止一條，路徑長度也可能不同。只有各條路徑上所有活動都完成了，整個工程才算完成。因此，完成整個工程所需的時間取決于從源點到匯點的最長路徑長度，即在這條路徑上所有活動的持續時間之和。這條路徑長度最長的路徑就叫做關鍵路徑。路徑長度：指路徑上的各邊權值之和。關鍵活動：關鍵路徑上的活動。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點源點 關鍵活動有關的量： 事件vj的最早發生時間ve(j): 從源點v0到vj的最長路徑長度。 事件vj的最

3、遲發生時間vl(j):保證匯點的最早發生時間不推遲的前提下，事件vj允許的最遲開始時間，等于ve(n-1)減去從vj到vn-1最長路徑長度。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點源點 ve(0)=0ve(1)= 6ve(2)= 4ve(3)= 5ve(4)= 7ve(5)= 7ve(6)= 16ve(7)= 14ve(8)= 18vl(8)= 18vl(7)= 14vl(6)= 16vl(5)= 10vl(4)= 7vl(3)= 8vl(2)= 6vl(1)= 6vl(0)= 0 關鍵活動有關的量： 活動ai的最早開始

4、時間e(i): 設活動ai在有向邊上, e(i)是從源 點v0到vj的最長路徑長度。因此e(i)=ve(j)。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點源點 關鍵活動有關的量： 活動ai的最遲開始時間l(i): l(i) 是在不會引起時間延誤的前提下，該活動允許的最遲開始時間。設活動ai在有向邊上, 則 l(i)= vl(k)-weight()325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點源點 aie(i)l(i) 0 0 0 6 4 5 7 7 7 16

5、 14 0 2 3 6 6 8 7 7 10 16 14 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 關鍵活動： l(i) e(i) 表示活動ak 是沒有時間余量的關鍵活動。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點源點為找出關鍵活動, 需要求各個活動的 e(i) 與 l(i)，以判別是否 l(i) e(i) 為求得e(i) 與 l(i)，需要先求得從源點V0到各個頂點Vj 的 ve(j) 和 vl(j)。求關鍵活動算法求關鍵活動的基本步驟：對AOE網進行拓撲排序，按拓撲次序求出各頂點事件的最早發

6、生時間ve，若網中有回路，則終止算法； 按拓撲序列的逆序求各頂點事件的最遲發生時間vl;根據ve和vl的值，求各活動的最早開始時間e(i)與最遲開始時間l(i)，若e(i)=l(i)，則i是關鍵活動。 例 求關鍵活動 第1步ve(k)ve(0)0 k=0maxve(j)+ weight() E(G), k=1, 2, , n-1325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點源點按拓撲正序遞推: ve(0)=0ve(1)= ve(0)+weight()=0+6=6ve(2)= ve(0)+weight()=0+4=4ve(3)=

7、 ve(0)+weight()=0+5=5ve(4)= maxve(1)+ weight()， ve(2)+ weight()=max6+1,4+1=7ve(5)= ve(3)+weight()=5+2=7ve(6)= ve(4)+weight()=7+9=16ve(7)= maxve(4)+ weight()， ve(5)+ weight()=max7+7,7+4=14ve(8)= maxve(6)+ weight()， ve(7)+ weight()=max16+2,14+4=18 例 求關鍵活動 第2步vl(j)ve(n-1) j=n-1minvl(k)- weight() E(G),

8、j= n-2, n-3,0325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點源點按拓撲逆序遞推: vl(8)= ve(8)=18vl(7)= vl(8)-weight()=18-4=14vl(6)= vl(8)-weight()=18-2=16vl(5)= vl(7)-weight()=14-4=10vl(4)= minvl(7)- weight()， vl(6)- weight() =min14-7,16-9=7vl(3)= vl(5)-weight()=10-2=8vl(2)= vl(4)-weight()=7-1=6vl(1

9、)= vl(4)-weight()=7-1=6vl(0)= minvl(1)- weight()， vl(2)- weight(), vl(3)- weight() = min6-6,6-4,8-5=0 aie(i)l(i)li-ei 0 0 0 6 4 5 7 7 7 16 14 0 2 3 6 6 8 7 7 10 16 14 0 2 3 0 2 3 0 0 3 0 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 例 求關鍵活動 第3步： e(i)=ve(j), l(i)=vl(k)-weight()325140867a1=6a8=7a7=9a6=2a4=1a5=

10、1a3=5a2=4a9=4a11=4a10=2匯點源點算法CriticalPath ()/* 圖的關鍵路徑算法 */CPath1計算事件的最早發生時間 FOR i = 1 TO n DO ve i 0. FOR i = 1 TO n1 DO/*（1）按頂點的拓撲序列計算各事件的最早發生時間*/ (padjacent(Head i) . WHILE p DO(k VerAdj (p) .IF (vei + cost (p) vek ) THENvek vei + cost (p) .plink(p)CPath2計算事件的最遲發生時間 FOR i = 1 TO n DO vli ven . FOR

11、 i = n1 TO 1 STEP 1 DO /*（2）按拓撲逆序計算事件的最遲發生時間*/ (padjacent (Headi) .WHILE p DO(kVerAdj(p) .IF (vlk cost (p) vli ) THENvli vlk cost(p) .plink(p)CPath3求諸活動的最早開始時間和最遲開始時間 FOR i = 1 TO n DO (padjacent (Head i) .WHILE p DO(kVerAdj (p) .evei .lvlk cost(p) .IF l = e THEN PRINT is Critical Activity! plink(p)

12、 時間復雜性： 對定點進行拓撲排序的時間復雜性為O(n+e), 以拓撲排序求vei和以拓撲逆序求vli時, 所需時間為均為O(e), 求各個活動的ek和lk的時間復雜度為O(e), 整個算法的時間復雜性是O(n+e)。定理 5.3 任意的非空AOE網至少存在一條關鍵路徑。 推論 5.1 假設邊屬于AOE網，則有且如果屬于某一條關鍵路徑，則有 第五章 圖5.1 基本概念5.2 圖的存儲結構5.3 圖的遍歷5.4 拓撲排序5.5 關鍵路徑 5.6 最短路徑5.7 最小支撐樹5.8 圖的應用5.6 最短路徑問題 兩頂點間可能存在多條路徑，每條路徑經過的邊數不同，每條路徑的各邊權值之和也不同。 從一個

13、指定的頂點到達另一指定頂點的路徑上各邊權值之和最小的路徑被稱為最短路徑，這類問題亦稱為最短路徑問題。 單源(由一個指定頂點到其他頂點)最短路徑 無權最短路徑 正權最短路徑 負權最短路徑每對頂點之間的最短路徑問題5.6.1 無權最短路徑問題無權所有邊的權值都為1源點到各頂點的路徑所經歷的邊的數目就是路徑的長度相對于源點由近及遠依次求各頂點的最短路徑算法思想：設Di為源點S到頂點 i 的最短路徑長度訪問初始頂點S，即令DS=0。從S出發，找最短路徑為1的頂點，即S的所有鄰接頂點w，令Dw=DS+1從上步訪問的頂點w出發，找最短路徑為2的頂點，即w未被訪問的鄰接頂點v，令Dv=Dw+1繼續上述過程，

14、直至處理完所有頂點。1V12V63V51V32V43V20SV0 例V1V6V5V3V4V21122330SV0上述過程中，訪問頂點的次序與對圖進行廣度優先遍歷的次序是一致的;初始時，令Dw=-1，當Dw由-1變成一個正整數時，表示從源點到w的最短路徑已求完，Dw值就是最短路徑長度,實現時使用數組dist 存儲;為了找到最短路徑，使用path 存儲從源點到頂點 i 的最短路徑上最后一個經歷的頂點。寬度優先遍歷 將所有頂點的visited值置為0, 訪問初始頂點v0 ，置visitedv0=1，v0入隊； 檢測隊列是否為空，若隊列為空，則迭代結束； 從隊頭取出一個頂點v，檢測其每個鄰接節點w：

15、如果w未被訪問過，則 訪問w； 將visitedw值更新為1； 將w入隊； 執行步驟 。算法ShortestPath(v, n)/* 計算從頂點v到其他各頂點的最短路徑*/SPath1初始化 CREATQ(Q) . /* 創建一個隊列 */ FOR i = 1 TO n DO (pathi -1. disti -1.) distv 0 . Qv.SPath2求從頂點v到其他各頂點的最短路徑 WHILE NOT(ISEMTQ(Q) DO ( u Q . /* 隊頭頂點u出隊 */ p adjacent (Headu) . /* p為u的邊鏈表的頭指針 */ WHILE p DO ( k VerA

16、dj (p) . IF (distk = -1) THEN ( Q k. / 將u的未訪問的鄰接頂點入隊 distk distu + 1. /修改其path值和dist值 pathk u)p link(p) . ) ) 1V12V63V51V32V43V20SV0 在最短路徑的計算中，一個頂點入隊出隊各一次，時間復雜性為O(n)，而對每個頂點，都要對它的邊鏈表進行遍歷，其遍歷鄰接表的開銷為O(e)，于是整個算法的時間復雜性為O(n+e)。 5.6.2 正權最短路徑問題問題： 給定一個帶權有向圖D（限定各邊上的權值大于或等于0）與源點v，求從v到D中其它頂點的最短路徑。寬度優先策略還可行嗎？最短

17、路徑不一定恰好就是連接這兩個頂點的邊(若此邊存在)，而可能是一條包括一個或多個中間頂點的路徑。v0v1v2283 Dijkstra算法基本思想：將圖中所有頂點分成兩個集合，第一個集合S包括已確定最短路徑的頂點，第二個集合T包括尚未確定最短路徑的頂點。按照最短路徑長度遞增的順序逐個把第二組的頂點加到第一組中去，直至從源點出發可以到達的所有頂點都包括到第一組中。 Dijkstra算法描述初始時（S為初始頂點）, Ds=0且 i S，有Di =。在未訪問頂點中選擇Dv最小的頂點v，訪問v，令 Sv=1。依次考察v的鄰接頂點w，若 Dv+weight() Dw ， 則改變Dw的值，使Dw = Dv +

18、 weight() 。重復 ，直至所有頂點被訪問。為了找到最短路徑，使用path 存儲從S到 i 的最短路徑上最后一個經歷的頂點。定理7.1 Dijkstra算法可以按照非遞減次序依次得到各頂點的最小路徑長度。 當前正在訪問的節點v， Dv為源點到v的最短距離，對應的最短路徑是由已訪問節點組成；按照訪問的次序，該算法將生成一個節點序列，排在前面的節點距源點的距離小于等于排在后面節點距源點的距離。引入一個輔助數組dist。它的每一個分量disti表示當前找到的從源點s到頂點i 的最短路徑的長度。初始狀態： dists=0, 對其它節點i有disti=+ 。 pathi記錄s到i最短路徑中i的前驅

19、節點編號 例 1325810204530120234012340243105134303822541002024412 spathdist0000003421 01325810204530120234在未訪問頂點中選擇Dv最小的頂點v，訪問v，令 Sv=1。依次考察v的鄰接頂點w，若 Dv+weight() Dw ，則改變Dw的值，使Dw = Dv + weight() 。重復 ，直至所有頂點被訪問。0133023431325810204530120234spathdist10000034210303v0v0spathdist100010342103028311v0v0v1v132581330

20、02343028111325810204530120234 03421spathdist1100103028311v0 v1v1 v013258102045301202343120415813234231103421spathdist1100102315311v0v3v1v3132581020453012023431204158132342311120415813234231131325810204530120234spathdist1100102315311v0v3v1v3spathdist111110342102315311v0v3v1v3Dijkstra算法: 按照非遞減順序依次得到各頂

21、點的最小路徑長度。120415813234231131325810204530120234定理5.4 Dijkstra算法可以按照非遞減次序依次得到各頂點的最小路徑長度。 證明：歸納法算法得到的路徑值是各頂點的最小路徑長度。算法得到的路徑值是按非遞減次序得到的。算法DShortestPath(n, v)/* 計算v到其他各頂點的最短路徑 */DSPath1初始化 FOR i = 1 TO n DO ( pathi-1. disti max. si 0. )/ 數組si記錄i是否被訪問過 distv 0. sv 1. p adjacent (Headv) . u v. / u為即將訪問的頂點DS

22、Path2求從初始頂點v到其他各頂點的最短路徑 FOR j = 1 TO n-1 DO / 求從v到其他各頂點的最短路徑 (WHILE p DO /修改u鄰接頂點的path值和dist值 ( kVerAdj (p) . IF ( sk 1 AND distu + cost(p) 0 AND disti ldist AND si = 0 ) THEN( ldist disti . u i. ) su 1./ 訪問u p adjacent (Headu) ) / p為u的邊鏈表的頭指針該算法的時間復雜性為O(n2+e)，也可認為是O(n2)時間復雜性分析5.6.3 每對頂點間的最短路徑問題：已知一

23、個各邊權值均大于0的帶權有向圖，對每一對頂點 vi vj，求vi 與vj間的最短路徑和最短路徑長度。可依次把每個頂點作為源點，執行n次Dijkstra算法。Floyd算法：定義一個n階方陣序列： A(-1), A(0), , A(n-1).Floyd算法的基本思想：設鄰接矩陣存儲圖，定義初始矩陣A(-1) ij = Edgeij；1、求A(0),即從vi到vj 經由頂點可以是v0的最短路徑長度；2、求A(1),即從vi 到vj 經由頂點可以是v0, v1的最短路徑長度； n、求A(n-1),即從vi 到vj 經由頂點可以是v0, v1,vn-1的最短路徑長度； 其中 A(k) ij = min

24、 A(k-1)ij， A(k-1)ik + A(k-1)kj , k = 0,1, n-1 Floyd算法的基本思想： 定義一個n階方陣序列： A(-1), A(0), , A(n-1). 其中 A(-1) ij = Edgeij； A(k) ij = min A(k-1)ij， A(k-1)ik + A(k-1)kj , k = 1, n A(-1) ij是從頂點vi 到vj , 中間頂點是v0的最短路徑的長度, A(k) ij是從頂點vi 到vj , 中間頂點的序號不大于k的最短路徑的長度, A(n-1)ij是從頂點vi 到vj 的最短路徑長度。上式每迭代一次，在從頂點i到頂點j之間的最短

25、路徑就多考慮一個頂點。經過n次迭代后， A(k) i, j的值就是從頂點i到頂點j之間的最短路徑。 從A(3)知，頂點1到0的最短路徑長度為a10 = 11,其最短路徑看 path10 = 2，path12 = 3，path 13 = 1, 表示頂點0 頂點2 頂點3 頂點1; 從頂點1到頂點0最短路徑為,。 Floyd算法允許圖中有帶負權值的邊，但不許有包含帶負權值的邊組成的回路。 從A(3)知，頂點1到0的最短路徑長度為a10=11,其最短路徑 path10=2，path12=3，path 13=1, 表示頂點0頂點2 頂點3 頂點1;從頂點1到頂點0最短路徑為,。 算法 AllLengt

26、h ( n )/* 求每對頂點間的最短路徑 */ALength1初始化 FOR i=0 TO n-1 DO / 矩陣A和path初始化FOR j=0 TO n-1 DO( Aij edgeij ./ 初始化的A即A(-1) IF ( ij AND Aij max ) THENpathiji . ELSEpathij -1.)ALength2求圖中任意兩頂點的最短路徑 FOR k=0 TO n-1 DO /從A(-1)開始針對每個k逐步構造A(n-1) FOR i=0 TO n-1 DOIF (ik) THEN FOR j=0 TO n-1 DO IF(j k AND j i AND Aikma

27、x AND Akjmax AND Aik+AkjAij) THEN ( Aij Aik + Akj . pathijpathkj .) Floyd算法的時間復雜度為O(n3)，與調用n次Dijkstra算法求每對頂點的最短路徑的時間復雜度相同。 但Dijkstra算法僅針對正權圖，而Floyd算法允許圖中有帶負權值的邊，但不許有包含帶負權值的邊組成的回路；且Floyd算法更簡單易于理解。 本章給出的求解最短路徑的算法，不僅適用于帶權有向圖，對帶權無向圖也可以適用。因為帶權無向圖可以看作是有往返二重邊的有向圖。 第五章 圖5.1 基本概念5.2 圖的存儲結構5.3 圖的遍歷5.4 拓撲排序5.5

28、 關鍵路徑 5.6 最短路徑5.7 最小支撐樹5.8 圖的應用 5.7 最小支撐樹1、基本概念2、生成最小支撐樹算法 Prim算法 Kruskar算法最小支撐樹基本概念 對于一個無向網絡無向加權連通圖N=(V,E,C)(C表示該圖為權圖)，其頂點個數為|V|=n，圖中邊的個數為|E| ，我們可以從它的|E|條邊中選出n-1條邊，使之滿足 （1）這n-1條邊和圖的n個頂點構成一個連通圖。 （2）該連通圖的代價是所有滿足條件(1)的連通圖的代價的最小值。 這樣的連通圖被稱為網絡的最小支撐樹( Minimum-cost Spanning Tree )。 最小支撐樹的性質最小支撐樹中沒有回路 若MST

29、 的邊集中有回路，顯然可通過去掉回路中某條邊而得到花銷更小的MST最小支撐樹是一棵有|V| - 1條邊的樹最小支撐樹的邊集支撐起了圖中所有頂點，且邊集的代價最小最小支撐樹的應用使連接電路板上一系列接頭所需焊接的線路最短在n個城市間建立造價最低的通訊網絡 5.7 最小支撐樹1、基本概念2、生成最小支撐樹算法 Prim算法 Kruskar算法MST性質：N=(V, E, C)是一個連通網，U是V的一個非空子集，若u, v滿足weight(u, v)=min weight(u0, v0) | u0U, v0V-U則必存在N的一棵最小支撐樹，該支撐樹中包括邊(u, v)。 U V-U uv1、普里姆(

30、Prim)算法(逐點加入) 設N=(V,E,C)為連通網，TE是N的最小支撐樹MST的邊的集合，U為MST頂點集。 U=uo(uoV), TE= ； 找到滿足weight(u,v)minweight(u1,v1)|u1U, v1V-U, 的邊，把它并入TE，同時v并入U； 反復執行 ,直至 V=U , 算法結束。 4316504535562217 U V-U例431650453556221702143165045355622174316504535562217 U V-U402150214053221402154316504535562217 U V-U41053522143165045355

31、62217 U V-U4053221410535221 U V-U431650453556221743104535221假設用鄰接矩陣存儲圖。普里姆算法的實現需要增設兩個輔助數組closedgen和TEn-1 .closedgen的每個數組元素由兩個域構成：Lowcost和Vex，其定義如下：如果 ，則 = 而closedgev.Vex存儲的是該邊依附在U 中的頂點u.如果 ，則 數組TEn-1是最小支撐樹的邊集合，每個數組元素TEi表示一條邊，TEi由三個域head、tail和cost構成，它們分別存放邊的始點、終點和權值。 432156452314326515645562317131413

32、1641642314216452314326515645562317 Vclosedge123456UV-UVexLowcost-101611151max1max12 ,3 ,4 ,5,64326515645562317 U V-UPrim: FOR i = 1 TO n DO ( Lowcost (closedgei)edge1i . Vex (closedgei) 1) Vex (closedge1) -1. count 1. Vclosedge123456UV-UVexLowcost-101611151max1max12 ,3 ,4 ,5 ,6v 0. / 求當前權值最小的邊和該邊的終點

33、vminmax. FOR j = 1 TO n DO IF (vex (closedgej) -1 AND Lowcost(closedgej) min ) ( v j. min Lowcost (closedgej) ) Vclosedge123456UV-UVexLowcost-1016-10151max1max1,32, 4 ,5 ,6If v0 THEN / v加入U中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1./ 計數器加

34、1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1./ 頂點v進入集合U Vclosedge123456UV-UVexLowcost-1035-101535341,32,4 ,5,6 4326515645562317 U V-U FOR j = 1 TO n DO /修改某些頂點的值 IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej) THEN ( Lowcost(closedgej) edgevj . Vex(closedgej) v. ) )算法Prim( )/* 構造最小支撐樹的Prim算法

35、 */Prim1初始化鄰接矩陣 FOR i = 1 TO n DO FOR j = 1 TO n DO IF (edgeij = 0) edgeij = max; / max是預定義常數Prim2以頂點1為初始頂點，初始化數組closedge FOR i = 1 TO n DO ( Lowcost (closedgei)edge1i . Vex (closedgei) 1) Vex (closedge1) -1./ 頂點1進入集合U count 1. / 支撐樹的邊記數器countPrim3構造圖的最小支撐樹 FOR i =2 TO n DO / 循環n-1次 ( v 0. minmax. / 求當前權值最小的邊和該邊的終點v FOR j = 1 TO n DO IF (vex (closedgej) -1 AND Lowcost(closedgej) min ) THEN ( v j. min Lowcost (closedgej) . ) IF v0 THEN /將該邊加入TE中，點v加入集合U中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1./ 計數器加1 Lowcost (clos