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

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

3、部頂點的拓?fù)溆行蛐蛄械倪\算就叫做拓?fù)渑判?。如果通過拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂點都排入一個拓?fù)溆行虻男蛄兄? 則該網(wǎng)絡(luò)中必定不會出現(xiàn)有向環(huán)。第六張，PPT共三十二頁，創(chuàng)作于2022年6月如果AOV網(wǎng)絡(luò)中存在環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。例如, 對學(xué)生選課工程圖進(jìn)行拓?fù)渑判? 得到的拓?fù)溆行蛐蛄袨?C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6C8C3C5C4C9C6C7C1C2第七張，PPT共三十二頁，創(chuàng)作于2022年6月拓?fù)渑判虻姆椒?輸入AOV網(wǎng)絡(luò)。令

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

5、出頂點C4C5C1(f) 輸出頂點C1C5(g) 輸出頂點C5 最后得到的拓?fù)溆行蛐蛄袨?C2 , C0 , C3 , C4 , C1 , C5 。它滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對于本來沒有這種關(guān)系的頂點，如C2和C4，也排出了先后次序關(guān)系。(h) 拓?fù)渑判蛲瓿傻谑畯?，PPT共三十二頁，創(chuàng)作于2022年6月AOV網(wǎng)絡(luò)及其鄰接表表示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è)一個數(shù)組indegree ，記錄各頂點入度。在拓?fù)渑判蚯扒?初始化入度數(shù)組。入度為零的頂點即無前驅(qū)頂點。在算法中, 使用棧存放入度為零的頂點, 供選擇和輸出無前驅(qū)的頂點。第十二張，PPT共三十二頁，創(chuàng)作于2022年6月拓?fù)渑判蛩惴擅枋鋈缦拢喝攵葹榱愕捻旤c入棧;當(dāng)棧不空時, 重復(fù)執(zhí)行 從頂點棧中退出一個頂點, 并輸出之; 從AOV網(wǎng)絡(luò)中刪去這個頂點和它發(fā)出的邊, 邊的終頂點入度減一; 如果邊的終頂點入度減至0, 則該頂點進(jìn)棧; 如果輸出頂點個數(shù)少于AOV網(wǎng)絡(luò)的頂點個數(shù), 則報告網(wǎng)絡(luò)中存在有向環(huán)。第十三張，PPT共三十二頁，創(chuàng)作于2022年6月拓?fù)渑判虻乃惴╲oid Topolog

7、icalSort (ALGraph G) FindInDegree(G,indegree); /初始化indegree InitStack(S); for (i = 0; i G.vexnum; i+ ) /入度為零的頂點 if (indegreei = 0 ) Push(S, i); /進(jìn)棧 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 ); /頂點的入度減至零, 進(jìn)棧 第十五張，PPT共三十二頁，創(chuàng)作于2022年6月7.5.2 關(guān)鍵路徑一、AOE網(wǎng)如果在有向無環(huán)圖中, 用有向邊表示一個工程中的活動 (Activity), 用邊上權(quán)值表示活動持續(xù)時間 (Duration), 用頂點表示事件 , 則這樣的有向圖叫做用邊表示活動的網(wǎng)絡(luò), 簡稱 AOE ( Activity On Edges ) 網(wǎng)。第十六張，PPT共三十二頁，創(chuàng)作于2022年6月AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例如，可以使人們了解：完成整個工程至少需要多少時間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))? 為縮短完成工程所需的時間, 應(yīng)當(dāng)加快哪些活動?第十七張，PPT共三十

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

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

11、 l(i) = e(i) 的活動稱為關(guān)鍵活動。第二十一張，PPT共三十二頁，創(chuàng)作于2022年6月三、怎樣求關(guān)鍵路徑？ 如何找e(i)=l(i)的關(guān)鍵活動？為找出關(guān)鍵活動, 需要求各個活動的 e(i) 與 l(i)，以判別是否 l(i) = e(i)。 設(shè)活動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é)構(gòu)；從源點v0

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

15、e（全局變量），T為拓?fù)湫蛄许旤c棧 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的各項關(guān)鍵活動 if(!TopologicalOrder(G,T) return ERROR; vl0.G.vexnum-1=ve0.G.vexnum-1;/初始化頂點事件的最遲發(fā)生時間 while(!StackEmpty(T) /按逆拓?fù)溆行蚯蟾黜旤c的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和關(guān)鍵活動 for(p=G.verticesj；p；p=pnextarc) k=pa