拓撲排序與關鍵路徑

1、關于拓撲排序和關鍵路徑第一張，PPT共三十二頁，創(chuàng)作于2022年6月AOV-網(wǎng) 用頂點表示活動，用邊來表示活動之間的先后關系的有向圖稱為頂點活動網(wǎng)，簡稱AOV-網(wǎng)。例如，計算機專業(yè)學生的學習就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領先關系，有的課程可以并行地學習。7.5.1 拓撲排序第二張，PPT共三十二頁，創(chuàng)作于2022年6月 C1 高等數(shù)學 C2 程序設計基礎 C3 離散數(shù)學 C1, C2 C4 數(shù)據(jù)結(jié)構 C3, C2 C5 高級語言程序設計 C2 C6 編譯方法 C5, C4 C7 操作系統(tǒng) C4, C9 C8 普

2、通物理 C1 C9 計算機原理 C8 課程代號 課程名稱 先修課程第三張，PPT共三十二頁，創(chuàng)作于2022年6月學生課程學習工程圖C8C3C5C4C9C6C7C1C2第四張，PPT共三十二頁，創(chuàng)作于2022年6月在AOV網(wǎng)絡中不能出現(xiàn)回路, 即環(huán)。如果出現(xiàn)了環(huán)，則意味著某項活動應以自己作為先決條件，這是荒謬的。因此，對給定的AOV網(wǎng)絡，必須先判斷它是否存在有向環(huán)。第五張，PPT共三十二頁，創(chuàng)作于2022年6月檢測有向環(huán)的一種方法是對AOV網(wǎng)絡構造它的拓撲有序序列。即將各個頂點 (代表各個活動)排列成一個線性有序的序列，使得AOV網(wǎng)絡中所有應存在的前驅(qū)和后繼關系都能得到滿足。 這種構造AOV網(wǎng)全

3、部頂點的拓撲有序序列的運算就叫做拓撲排序。如果通過拓撲排序能將AOV網(wǎng)絡的所有頂點都排入一個拓撲有序的序列中, 則該網(wǎng)絡中必定不會出現(xiàn)有向環(huán)。第六張，PPT共三十二頁，創(chuàng)作于2022年6月如果AOV網(wǎng)絡中存在環(huán)，此AOV網(wǎng)絡所代表的工程是不可行的。例如, 對學生選課工程圖進行拓撲排序, 得到的拓撲有序序列為 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6C8C3C5C4C9C6C7C1C2第七張，PPT共三十二頁，創(chuàng)作于2022年6月拓撲排序的方法 輸入AOV網(wǎng)絡。令

4、n 為頂點個數(shù)。 在AOV網(wǎng)絡中選一個沒有直接前驅(qū)的頂點, 并輸出之; 從圖中刪去該頂點, 同時刪去所有它發(fā)出的有向邊; 重復以上 、步, 直到 全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或 圖中還有未輸出的頂點, 但已跳出處理循環(huán)。說明圖中還剩下一些頂點, 它們都有直接前驅(qū)。這時網(wǎng)絡中必存在有向環(huán)。第八張，PPT共三十二頁，創(chuàng)作于2022年6月C0C1C4C3C2C5拓撲排序的過程(a) 有向無環(huán)圖C4C5C1C0C3(b) 輸出頂點C2C1C4C5C3(c) 輸出頂點C0C2C0C4C5C1C3(d) 輸出頂點C3第九張，PPT共三十二頁，創(chuàng)作于2022年6月C1C4C5(e) 輸

5、出頂點C4C5C1(f) 輸出頂點C1C5(g) 輸出頂點C5 最后得到的拓撲有序序列為 C2 , C0 , C3 , C4 , C1 , C5 。它滿足圖中給出的所有前驅(qū)和后繼關系，對于本來沒有這種關系的頂點，如C2和C4，也排出了先后次序關系。(h) 拓撲排序完成第十張，PPT共三十二頁，創(chuàng)作于2022年6月AOV網(wǎng)絡及其鄰接表表示C0C1C4C3C2C5 C0 C1 C2 C3 0 C4 C5 0012345indegree data firstarc 130103 1adjvex nextarc 3 0 5 0 1 5 0 0 1 5 0第十一張，PPT共三十二頁，創(chuàng)作于2022年6月

6、在鄰接表中增設一個數(shù)組indegree ，記錄各頂點入度。在拓撲排序前前,初始化入度數(shù)組。入度為零的頂點即無前驅(qū)頂點。在算法中, 使用棧存放入度為零的頂點, 供選擇和輸出無前驅(qū)的頂點。第十二張，PPT共三十二頁，創(chuàng)作于2022年6月拓撲排序算法可描述如下：入度為零的頂點入棧;當棧不空時, 重復執(zhí)行 從頂點棧中退出一個頂點, 并輸出之; 從AOV網(wǎng)絡中刪去這個頂點和它發(fā)出的邊, 邊的終頂點入度減一; 如果邊的終頂點入度減至0, 則該頂點進棧; 如果輸出頂點個數(shù)少于AOV網(wǎng)絡的頂點個數(shù), 則報告網(wǎng)絡中存在有向環(huán)。第十三張，PPT共三十二頁，創(chuàng)作于2022年6月拓撲排序的算法void Topolog

7、icalSort (ALGraph G) FindInDegree(G,indegree); /初始化indegree InitStack(S); for (i = 0; i G.vexnum; i+ ) /入度為零的頂點 if (indegreei = 0 ) Push(S, i); /進棧 count=0; /對輸出頂點計數(shù) 第十四張，PPT共三十二頁，創(chuàng)作于2022年6月 while( ! StackEmpty(S) ) Pop( S, i ); /退棧 cout i nextarc) k = p-adjvex; if ( -indegreek = 0 ) /頂點入度減1 Push( S

8、, k ); /頂點的入度減至零, 進棧 第十五張，PPT共三十二頁，創(chuàng)作于2022年6月7.5.2 關鍵路徑一、AOE網(wǎng)如果在有向無環(huán)圖中, 用有向邊表示一個工程中的活動 (Activity), 用邊上權值表示活動持續(xù)時間 (Duration), 用頂點表示事件 , 則這樣的有向圖叫做用邊表示活動的網(wǎng)絡, 簡稱 AOE ( Activity On Edges ) 網(wǎng)。第十六張，PPT共三十二頁，創(chuàng)作于2022年6月AOE網(wǎng)絡在某些工程估算方面非常有用。例如，可以使人們了解：完成整個工程至少需要多少時間(假設網(wǎng)絡中沒有環(huán))? 為縮短完成工程所需的時間, 應當加快哪些活動?第十七張，PPT共三十

9、二頁，創(chuàng)作于2022年6月從源點到匯點的路徑可能不止一條，并且這些路徑的長度也可能不同。 完成不同路徑的活動所需的時間雖然不同, 但只有各條路徑上所有活動都完成了, 整個工程才算完成。因此, 完成整個工程所需的時間取決于從源點到匯點的最長路徑長度, 即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關鍵路徑(Critical Path)。第十八張，PPT共三十二頁，創(chuàng)作于2022年6月要找出關鍵路徑，必須找出關鍵活動, 即不按期完成就會影響整個工程完成的活動。關鍵路徑上的所有活動都是關鍵活動。因此, 只要找到了關鍵活動, 就可以找到關鍵路徑。例如, 下圖就是一個AOE網(wǎng)。V1V

10、3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1第十九張，PPT共三十二頁，創(chuàng)作于2022年6月二、相關術語 事件Vi 的最早發(fā)生時間ve(i) 是從源點V0 到頂點Vi 的最長路徑長度。 事件Vi 的最遲發(fā)生時間vl(i) 在不推遲整個工程完成的前提下，事件Vi 的最遲發(fā)生時間。 活動ai 的最早開始時間 e(i) 活動ai 的最遲開始時間 l(i) 表示在不推遲整個工程完成的前提下，活動ai最遲必須開始進行的事件。第二十張，PPT共三十二頁，創(chuàng)作于2022年6月 時間余量 l(i) e(i) 表示活動 ai 的最早可能開始時間和最遲允許開始時間的時間余量。

11、 l(i) = e(i) 的活動稱為關鍵活動。第二十一張，PPT共三十二頁，創(chuàng)作于2022年6月三、怎樣求關鍵路徑？ 如何找e(i)=l(i)的關鍵活動？為找出關鍵活動, 需要求各個活動的 e(i) 與 l(i)，以判別是否 l(i) = e(i)。 設活動ai由弧表示， 且活動持續(xù)時間記為dut(), 則 e(i) = ve(j) l(i) = vl(k) - dut()VjVkai第二十二張，PPT共三十二頁，創(chuàng)作于2022年6月 如何求ve(i)和vl(i)？求ve(i)的遞推公式 從 ve(0)= 0 開始，向前遞推 T, i = 1, 2, , n-1 T 是所有以第j個頂點為頭的弧

12、的集合。例，求右圖中頂點V6的最早發(fā)生時間。V3V4V5V6a6=3a7=2a8=1266第二十三張，PPT共三十二頁，創(chuàng)作于2022年6月V1V2V3V4V5V6頂點 ve vl032668V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1032668第二十四張，PPT共三十二頁，創(chuàng)作于2022年6月求vl(i)的遞推公式 從vl(n-1) = ve(n-1)開始，反向遞推 S, i = n-2, n-3, , 0S是所有以第i個頂點為尾的弧的集合。 例，求右圖中頂點V1的最遲發(fā)生時間。V1V3V2a1=3a2=224第二十五張，PPT共三十二頁，創(chuàng)作于

13、2022年6月V1V2V3V4V5V6頂點 ve vl032668V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1042678042678第二十六張，PPT共三十二頁，創(chuàng)作于2022年6月a1a2a3a4a5a6a7a8活動 e l l-e011000341220253660671341V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1V1V2V3V4V5V6頂點 ve vl032668042678第二十七張，PPT共三十二頁，創(chuàng)作于2022年6月四、算法實現(xiàn)實現(xiàn)步驟：輸入e條弧，建立AOE-網(wǎng)的存儲結(jié)構；從源點v0

14、出發(fā)，令ve0=0，按拓撲有序求其余各頂點的最早發(fā)生時間vei（1in-1）。如果得到的拓撲有序序列中頂點個數(shù)小于網(wǎng)中頂點數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關鍵路徑，算法終止；否則執(zhí)行步驟。從匯點vn出發(fā)，令vln-1=ven-1，按逆拓撲有序求其余各頂點的最遲發(fā)生時間vli（n-2i2）；根據(jù)各頂點的ve和vl的值，求每條弧s的最早發(fā)生時間e(s)和最遲發(fā)生時間l(s)。若某條弧滿足條件e(s)=l(s)，則為關鍵活動。第二十八張，PPT共三十二頁，創(chuàng)作于2022年6月 算法實現(xiàn)Status TopologicalOrder(ALGraph G,Stack &T) /求各頂點事件的最早發(fā)生時間v

15、e（全局變量），T為拓撲序列頂點棧 FindInDegree(G,indegree)； /對各頂點求入度 InitStack(T)；count=0； ve0.G.vexnum-1=0； /初始化 while(!StackEmpty(S) /S為零入度頂點棧 Pop(S,j)； push(T,j)； +count； /j號頂點入T棧并計數(shù) for(p=G.verticesj.firstarc； p； p=pnextarc) k=padjvex； /對j號頂點的每個鄰接點的入度減1 if(-indegreek=0) push(S,k)； if(vej+*(pinfo)vek) vek=vej+*(

16、pinfo)； if(countG.vexnum) return ERROR； /該有向網(wǎng)有回路 else return OK；第二十九張，PPT共三十二頁，創(chuàng)作于2022年6月Status CriticalPath(ALGraph G) /G為有向網(wǎng)，輸出G的各項關鍵活動 if(!TopologicalOrder(G,T) return ERROR; vl0.G.vexnum-1=ve0.G.vexnum-1;/初始化頂點事件的最遲發(fā)生時間 while(!StackEmpty(T) /按逆拓撲有序求各頂點的vl值 for(pop(T,j),p=G.verticesj.firstarc；p；p=pnextarc) k=padjvex； dut=*(pinfo)； if(vlk-dutvlj) vlj=vlk-dut； for(j=0；jG.vexnum；+j) /求ee，el和關鍵活動 for(p=G.verticesj；p；p=pnextarc) k=pa