數(shù)據(jù)結構,拓撲排序和關鍵路徑課件

1、第五章 拓撲排序和關鍵路徑吉林大學計算機學院谷方明fmgu2002問題背景計劃、施工過程、生產(chǎn)流程、程序流程等都可以看作一個任務或“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子任務?；顒又g一般會有先后關系。如果不違反限制完成這些活動，那么整個工程順利完成。例：選課計算機專業(yè)學生的學習就是一個工程，每一門課程的學習就是整個工程的一項活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有先后關系，有的課程可以并行地學習。任務：安排一種學習次序，使得所有課程都學習完成，并滿足課程的限制關系。計算機專業(yè)必修課程課程代號 課程名稱 先修課程 C0 高等數(shù)學 無 C1 程

2、序設計基礎 無 C2 離散數(shù)學 C0,C1 C3 數(shù)據(jù)結構 C2,C4 C4 程序設計語言 C1 C5 編譯技術 C3,C4 C6 操作系統(tǒng) C3,C8 C7 普通物理 C0 C8 計算機原理 C7 C0C2C3C5C4C1C7C6C8在有向圖中，用頂點表示活動，用有向邊表示活動之間的先后關系，稱這樣的有向圖為AOV網(wǎng)(Activity On Vertex Network)。拓撲序列：把AOV網(wǎng)中的所有頂點排成一個線性序列，該序列滿足如下條件：如果存在有向邊，則在該序列中，Vi 必位于Vj 之前。拓撲排序：構造AOV網(wǎng)的拓撲序列的過程被稱為拓撲排序。一種可能的拓撲序列是：C0 , C1 , C

3、2 , C4 , C3 , C5 , C7 , C8 , C6C0C2C3C5C4C1C7C6C8拓撲序列的存在性任意AOV網(wǎng)中拓撲序列不一定存在。例如，存在回路的AOV網(wǎng)就無法找到拓撲序列。因為出現(xiàn)了有向環(huán)，則意味著某項活動應以自己作為先決條件。有向無環(huán)圖一定存在拓撲序列。構造方法引理5.1： 設圖G = (V, E)是有向無環(huán)圖, V(G), 則G中一定存在入度為零的頂點。構造方法： 從網(wǎng)中選擇一個入度為0的頂點且輸出之。 從網(wǎng)中刪除該頂點及其所有出邊。執(zhí)行 ，直至所有頂點已輸出，或網(wǎng)中剩余頂點入度均不為0 （說明網(wǎng)中存在回路）。C0 , C1 , C2 , C4 , C3 , C5 ,

4、C7 , C8 , C6C0 , C1 , C4 , C2 , C3 , C5 , C7 , C8 , C6C0 , C1 , C7 , C2 , C4 , C3 , C5 , C8 , C6C0C2C3C5C4C1C7C6C8算法設計AOV網(wǎng)用鄰接表的形式存儲；數(shù)組count ，counti的值是頂點i的入度；使用一個數(shù)據(jù)結構，存放入度為0的點。線性表存放時發(fā)生在一端；取用順序無所謂，在同一端（棧）或另一端（隊列）。棧的模擬利用變量top和count數(shù)組元素的值來模擬堆棧的壓入和彈出。原理：利用入度為0的counti空間記錄棧元素的下標；top始終記錄棧頂元素的下標。拓撲排序算法算法Topo

5、Order( ) /* 圖的拓撲排序算法，n表示頂點數(shù) */T1初始化 for( i = 1 ; i= n ; i + ) counti = 0; for( i = 1 ; ilink ) count p-VerAdj +; for( i = 1 ; i= n ; i + ) if( counti = 0 ) counti = top , top = i ;002123124536count436251toptop-102123124536count-112123124536countT2拓撲排序 for( i = 1 ; i = n ; i+ ) if ( top = - 1 ) cout“

6、有回路! ”; RETURN; j = top , top = counttop . /* 彈出棧頂j */ cout link) k = p - VerAdj ; countk - ;/ 頂點k的入度減1 if (countk = 0 ) countk=top, top = k; 436251-111013124536counttop-112123124536counttop模擬棧的狀態(tài)初始化： top = -1;棧 空： top = -1入棧：counti = top; top = i;出棧：j = top; top = counttop;算法分析定理5.2 設G=(V, E)是有向無環(huán)圖

7、，V(G)=1, 2 , n, e=|E(G)|. 則算法TopoOrder是正確的且算法的時間復雜性為 O(n+e).正確性證明：初始化T1時，棧不為空T2時，如果G不空，棧也不空。輸出n個頂點結束設是邊，則 v 一定 排在 w 之前。拓展拓撲排序與有向環(huán)無回路的AOV網(wǎng)，其頂點可排成拓撲序列；有回路的AOV網(wǎng)，找不到所有頂點的拓撲序列；如果能將AOV網(wǎng)的所有頂點排成拓撲序列，則該AOV網(wǎng)中必定無有向環(huán)；如果得不到所有頂點的拓撲序列，則說明AOV網(wǎng)中存在有向環(huán)(AOV網(wǎng)所代表的工程是不可行的)。拓撲序列的個數(shù)關鍵路徑時間約束邊表示活動(Activity) 邊的權值表示活動的持續(xù)時間(Dura

8、tion) 頂點表示入邊的活動已完成，出邊的活動可以開始的狀態(tài)，也稱為事件(Event)這樣的有向無環(huán)帶權圖叫做AOE (Activity On Edges)網(wǎng)。例 某工程源點：表示整個工程的開始（入度為零）。匯點：表示整個工程的結束（出度為零）。完成整個工程至少需要多少時間？為縮短工程的時間，應當加快哪些活動？為了不延誤整個工期，哪些活動不得延期，哪些可適當延期436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2匯點源點a6=1關鍵路徑和關鍵活動AOE網(wǎng)中，有些活動可并行進行。只有各條路徑上所有活動都完成了，整個工程才算完成。因此，

9、完成整個工程所需的時間取決于從源點到匯點的最長路徑長度。路徑長度等于路徑上各邊的權之和。這條具有最大長度的路徑就叫做關鍵路徑。關鍵活動：不按期完成就會影響整個工期的活動。 關鍵路徑上的活動為關鍵活動；從源點到匯點由關鍵活動構成的路徑為關鍵路徑。436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2匯點源點a6=1關鍵活動有關的量 事件vj的最早發(fā)生時間 ve( j ): 從源點v0到vj的最長路徑長度。436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2匯點源點a6=1ve(1

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

11、i的最早開始時間e(i): 設活動ai為有向邊，則 e(i) = ve(j)。 ve(j)是從源點v0到vj的最長路徑長度，決定了所有從vj開始的活動的最早開始時間。 活動ai的最遲開始時間 l(i): l(i) 是在不會引起工期延誤的前提下，該活動允許的最遲開始時間。設活動ai為有向邊, 則 l(i) = vl(k)-weight()。vl(9)= 19vl(8)= 15vl(7)= 17vl(6)= 11vl(5)= 7vl(4)= 9vl(3)= 6vl(2)= 6vl(1)= 0ve(1)=0ve(2)= 6ve(3)= 4ve(4)= 5ve(5)= 7ve(6)= 7ve(7)=

12、16ve(8)= 15ve(9)= 19436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2a6=1aie(i)l(i)li-ei 0 0 0 6 4 4 5 7 7 7 16 15 0 2 4 6 6 10 9 8 7 11 17 15 0 2 2 0 2 5 3 1 0 4 0 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 關鍵活動： l(i) e(i) 表示活動ak 是沒有時間余量的關鍵活動。為找出關鍵活動, 需要求各個活動的 e(i) 與 l(i)，以判別是否 l(i) e(i) 為求得e(

13、i) 與 l(i)，需要先求得從源點V0到各個頂點Vj 的 ve(j) 和 vl(j)。436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2匯點源點a6=1求關鍵活動算法 對AOE網(wǎng)拓撲排序;（若網(wǎng)中有回路，則終止算法） 按拓撲次序求出各頂點事件的最早發(fā)生時間ve; 按拓撲序列的逆序求各頂點事件的最遲發(fā)生時間vl; 根據(jù)ve和vl的值，求各活動的最早開始時間e(i)與最遲開始時間l(i)，若e(i)=l(i)，則i是關鍵活動。 例 求關鍵活動 第1步ve(k) ve(k)ve(1)0 k=1maxve(j)+ weight() E(G

14、), k=2, 3, , n按拓撲正序遞推:436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2匯點源點a6=1ve(1)=0ve(2)= ve(1)+weight()=6ve(3)= ve(1)+weight()=4ve(4)= ve(1)+weight()=5ve(5)= maxve(2)+ weight()， ve(3)+ weight()=max6+1,4+1=7ve(6)= maxve(3)+ weight()， ve(4)+ weight()=max4+1,5+3=7ve(7)= ve(4)+weight()=7+9=16

15、ve(8)= maxve(4)+ weight()， ve(5)+ weight()=max7+8,7+4=15ve(9)= maxve(6)+ weight()， ve(7)+ weight()=max16+2,15+4=19436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2a6=1例 求關鍵活動 第2步vl(k) vl(j)ve(n) j=nminvl(k)- weight() E(G), j= n-1, n-2,1按拓撲逆序遞推:436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12

16、=4a11=2匯點源點a6=1vl(9)= ve(9)=19vl(8)= vl(9)-weight()=15vl(7)= vl(9)-weight()=17vl(6)= vl(8)-weight()=11vl(5)= minvl(8)- weight()， vl(7)- weight() =min15-8,16-9=7vl(4)= vl(6)-weight()=11-2=9vl(3)= minvl(6)- weight()， vl(5)- weight() =min11-1,7-1=6vl(2)= vl(5)-weight()=7-1=6vl(1)= minvl(2)- weight()， v

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

18、8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2匯點源點a6=1圖的關鍵路徑算法 算法CriticalPath ( )/* 圖的關鍵路徑算法 */CPath1計算事件的最早發(fā)生時間 for ( i = 1 ; i = n ; i + ) ve i = 0; for ( i = 2 ; i link) k =p - VerAdj ； if (vei + p - cost vek ) vek =vei + p - cost ; CPath2計算事件的最遲發(fā)生時間 for ( i = 1 ; i = 1 ; i - ) /*按拓撲逆序*/ for ( p = Head i . adjacent ; p ; p = p- link) k =p - VerAdj ； if (vlk p- cost cost ;CPath3求諸活動的最早開始時間和最遲開始時間 fo