數(shù)據(jù)結(jié)構(gòu)拓?fù)渑判蛘n件

1、數(shù) 據(jù) 結(jié) 構(gòu) DATA STRUCTURE, DS 拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)課程內(nèi)容圖結(jié)構(gòu)的應(yīng)用3 拓?fù)渑判驁D結(jié)構(gòu)的應(yīng)用4 關(guān)鍵路徑8.7 拓?fù)渑判颍╰opological sort）先決條件問題拓?fù)渑判驅(qū)⒁粋€有向無環(huán)圖中所有頂點在不違反先決條件關(guān)系的前提下排成線性序列的過程稱為拓?fù)渑判驅(qū)W生選修課程問題：學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)下列課程，才能無矛盾、順利地完成學(xué)業(yè)？課程代號課程名稱 先修課C1程序設(shè)計基礎(chǔ)無C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1,C2C4匯編語言C1C5語言的設(shè)計和分析C3,C4C6計算機原理C11C7編譯原理C3.C5C8操作系統(tǒng)C3,C6C9高等數(shù)學(xué)無 C10線性代數(shù)C9C11普通物理C

2、9C12數(shù)值分析C1,C9,C10C1C2C3C4C5C6C7C8C9C10C11C12數(shù)學(xué)模型：有向無環(huán)圖頂點活動（課程）有向弧活動i是活動j的先決條件序列1：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8序列2：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8Activity OnVertex network8.7 拓?fù)渑判颍ɡm(xù)）拓?fù)湫蛄?Topological order)對于有向無環(huán)圖G=(V, E), 所有頂點組成的線性序列如果滿足若在有向無環(huán)圖G中從頂點Vi到Vj有一條路徑，則在序列中頂點Vi必在頂點Vj之前則該線性序列可稱

3、作一個拓?fù)湫蛄?。拓?fù)湫蛄胁晃ㄒ?.7 拓?fù)渑判颍ɡm(xù)）任何有向無環(huán)圖G的所有頂點都可以排在一個拓?fù)湫蛄欣?。拓?fù)渑判虻姆椒ㄊ牵?、從圖G中選擇一個入度為0的頂點并輸出。2、從圖G中刪掉此頂點及其所有的出邊。3、回到第1步繼續(xù)執(zhí)行，直至G所有頂點都被輸出或G中不存在入度為0的頂點。C1C2C3C4C5C6C7C8C9C10C11C12C2C3C4C5C6C7C8C9C10C11C12（1）拓?fù)湫蛄校篊1C3C4C5C6C7C8C9C10C11C12（2）拓?fù)湫蛄校篊1-C2C4C5C6C7C8C9C10C11C12（3）拓?fù)湫蛄校篊1-C2-C3C5C6C7C8C9C10C11C12（4）拓?fù)湫蛄校?/p>

4、C1-C2-C3-C4C6C8C10C11C12（7）拓?fù)湫蛄校篊1-C2-C3-C4 -C5-C7-C9C6C8C11C12（8）拓?fù)湫蛄校篊1-C2-C3-C4 -C5-C7-C9-C10C6C7C8C9C10C11C12（5）拓?fù)湫蛄校篊1-C2-C3-C4 -C5C6C8C9C10C11C12（6）拓?fù)湫蛄校篊1-C2-C3-C4 -C5-C7C6C8C12（9）拓?fù)湫蛄校篊1-C2-C3-C4 -C5-C7-C9-C10-C11C8C12（10）拓?fù)湫蛄校篊1-C2-C3-C4 -C5-C7-C9-C10-C11-C6C8（11）拓?fù)湫蛄校篊1-C2-C3-C4 -C5-C7-C9-

5、C10-C11-C6 -C12（12）拓?fù)湫蛄校篊1-C2-C3-C4 -C5-C7-C9-C10-C11-C6 -C12-C8拓?fù)渑判蛩惴ㄊ紫刃枰嬎愀黜旤c的入度，然后在拓?fù)渑判蜻^程中，當(dāng)某個頂點的入度為零時，就將此頂點輸出，同時將該頂點的所有直接后繼頂點的入度減1。為了避免重復(fù)檢測入度為零的頂點，設(shè)立一個棧（或隊列），以保存當(dāng)前所有“入度為零”的頂點若有向G中所有頂點都被輸出，則表明G中沒有有向環(huán)，拓?fù)渑判虺晒?。若僅輸出了部分頂點，G中已不存在入度為0的頂點，則表明G中存在有向環(huán)，拓?fù)渑判蚴　Ｍ負(fù)渑判蛩惴▽崿F(xiàn)：設(shè)圖G的頂點數(shù)為n1、對各頂點求入度2、初始化棧S3、把所有入度為0的頂點入棧

6、S4、當(dāng)棧S非空時循環(huán)4.1 訪問棧頂元素v并出棧；4.2 獲得所有與v鄰接的未被訪問的頂點w4.3 把w的入度減1；4.4 若w的入度為0則入棧S直至棧S空為止5、如果存在頂點未被訪問，則有向圖有環(huán)，不存在拓?fù)湫蛄?，拓?fù)渑判蚴?；否則，拓?fù)渑判虺晒?、結(jié)束987645321123456789 data adjhead12546 7 8840123456783dest next7棧(底-頂)拓?fù)湫蛄?v13,2,1v23,2v33,4v53,6v73v45v67v88v9空例如：8.7 拓?fù)渑判颍ɡm(xù)）拓?fù)渑判蛩惴ǖ臅r間復(fù)雜度分析關(guān)鍵是，算法在開始時要找出所有入度為0的頂點（同時可知道其它頂點的

7、入度）當(dāng)采用鄰接矩陣時，算法在開始時找所有入度為0的頂點需要 O (n2)的時間，加上處理邊、頂點的時間，總代價為O(n2+e+n)= O (n2)當(dāng)采用鄰接表時，因為在頂點表的每個頂點中可以有一個字段來存儲入度，所以算法在開始時找所有入度為0的頂點只需要O(e)的時間，加上處理邊、頂點的時間，總代價為O(n+2e)=O(n+e)工程計劃有關(guān)問題把工程計劃表示為有向無環(huán)圖G，用頂點表示事件，弧表示活動，權(quán)表示活動持續(xù)時間。每個事件表示在它之前的活動已完成，在它之后的活動可以開始（約束條件）例：設(shè)一個工程有m=11項活動，n=9個事件，其中事件vj 事件v1表示整個工程開始(記為v) 事件v9表

8、示整個工程結(jié)束(記為vn) 活動ai用弧表示，其持續(xù)時間記為dut()問題：（1）完成整項工程至少需要多少時間？ （2）哪些活動是影響工程進(jìn)度的關(guān)鍵活動？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=48.8 關(guān)鍵路徑定義1AOE網(wǎng)(Activity On Edge network, 邊表示活動的網(wǎng))是一個頂點表示事件，弧表示活動，權(quán)表示活動持續(xù)時間的帶權(quán)有向無環(huán)圖。網(wǎng)中僅存在一個入度為0的頂點，稱作開始頂點；網(wǎng)中僅存在一個出度為0的頂點，稱為結(jié)束頂點距離路徑上各活動持續(xù)時間之和關(guān)鍵路徑從開始頂點到結(jié)束頂點的距離最長的路徑 由于AO

9、E網(wǎng)中某些活動可以同時進(jìn)行，要保證每個活動都能無矛盾順利完成(約束條件)，完成該工程的最少時間就是該工程AOE網(wǎng)的關(guān)鍵路徑距離。987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4定義2Ve(j)表示事件vj的最早(early)發(fā)生時間，是從開始頂點v到vj的最長路徑距離。其中Ve(n)是該工程AOE網(wǎng)的關(guān)鍵路徑距離。?如何計算Vl(j)表示事件vj的最遲(last)發(fā)生時間，是在不推遲整個工程完成(即保證結(jié)束頂點vn在Ve(n)時刻發(fā)生)的前提下,該事件最遲必須發(fā)生的時間。Vl(j)=Ve(n) 頂點vj到結(jié)束頂點vn的最長路徑距離。

10、？如何計算987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4064577161418987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4Ve示例0668710161418Vl示例定義3e(i)表示活動ai的最早(early)開始時間，是該活動的起點所表示事件的最早發(fā)生時間如果邊表示活動ai，則有e(i)=Ve(j)l(i)表示活動ai的最遲(last)開始時間，是該活動的終點所表示事件的最遲發(fā)生時間與該活動的所需時間之差如果邊表示活動ai，則有l(wèi)(i)=Vl(k)-dut()9

11、87645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40645771614007e示例06687101614732l示例0645771614180668710161418vjvkai定義4l(i)-e(i)表示完成活動ai的時間余量，它是在不增加完成整個工程所需時間的情況下，活動ai可以拖延的時間關(guān)鍵活動關(guān)鍵路徑上的活動，即l(i)=e(i)的活動987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9

12、=4a10=2a11=4987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40645771614007計算e06687101614732計算l987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4關(guān)鍵路徑如何找e(i)=l(i)的關(guān)鍵活動？設(shè)事件數(shù)為n，活動數(shù)為m。活動ai用弧表示，其持續(xù)時間記為dut()，則有：（1）e(i)=Ve(j)（2）l(i)=Vl(k) -dut()vjvkai如何求Ve(j)和Vl(j)？繼而如何求e(i)和l(i)？(1) Ve計算從開始頂點向后遞

13、推。Ve(j)的計算必須在vj的所有前驅(qū)頂點vk的Ve(k)全部計算出來以后才能進(jìn)行。因此，可以在拓?fù)渑判蛩惴ㄖ卸x一個大小為n的數(shù)組Ve, Vej初值為0。按照拓?fù)湫蛄星蟾黜旤cvk的Vek ，并利用Vek對vk的每一后繼頂點vj修正Vej。網(wǎng)采用鄰接表，給每個結(jié)點增加活動編號域active和活動持續(xù)時間域dut。(2) 同時設(shè)置一大小為m的數(shù)組e，對每一事件vj，可從鄰接表中找到從vj發(fā)出的每一條有向邊和邊序號i，ei=Vej。(3)Vl計算從結(jié)束頂點開始向前遞推。 Vl(j)的計算必須在vj的所有后繼頂點的最遲發(fā)生時間全部計算出來以后才能進(jìn)行。定義一個大小為n的數(shù)組Vl,Vlj初值為Ven

14、。實際上,按照在計算Ve時得到的 拓?fù)湫蛄心嫘颍来斡嬎愀黜旤cvk的Vlk, 并利用Vlk按照遞推公式對vk的每一個前驅(qū)頂點vj修正Vlj 。(4)設(shè)置一大小為m的數(shù)組l，計算出Vl后，掃描每一個弧結(jié)點，得弧的終點k、權(quán)和該弧序號i，li=Vlk- dut()。AOE網(wǎng)的鄰接表987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4AOE網(wǎng)AOE網(wǎng)的存儲結(jié)構(gòu)采用鄰接表102131415261718292 data Id adj1612425264146 977 4 982108411415012345678353dest dut activ

15、e next778給每個頂點增加域Id，用于存放事件的入度，給每個邊增加兩個域dut和active，用于存放活動的持續(xù)時間和活動的編號。987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4064577161418計算各事件最早發(fā)生時間Ve和各活動最早開始時間e的過程棧(底-頂)拓?fù)湫蛄衯1v2v3v4v5v6v7v8v90v10000000003,2,1v20645000003,2v306456+1=700003,4v506454+1=5 700003,6v70645707+9=167+7=1403v4064570161416+2=18

16、5v6064575+2=71614187v8064577167+7=1414188v9064577161414+4=1818空064577161418 活動ai a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e(j) 0 0 0 6 4 5 9 7 7 16 140645771614007事件j 1 2 3 4 5 6 7 8 9 Ve(j) 0 6 4 5 7 7 16 14 18前已求得拓?fù)湫蛄袨?其逆拓?fù)湫蛄袨?置Vl(9)=18,Vl(8)=Vl(9)-dut()=18-4=14Vl(6)=Vl(8)-dut()=14-4=10Vl(4)=Vl(6)-dut()

17、=10-2=8Vl(7)= Vl(9)-dut()=18-2=16Vl(5)=minVl(7)-dut(), Vl(8)-dut()=7Vl(3)=Vl(5)-dut()=7-1=6Vl(2)=Vl(5)-)-dut(), Vl(3)-dut()=min0,2=0求得圖中所dut()=7-1=6Vl(1)=minVl(2有事件的最遲發(fā)生時間如下:987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40668710161418事件j 1 2 3 4 5 6 7 8 9 Vl(j) 0 6 6 8 7 10 16 14 18活動ai a1 a

18、2 a3 a4 a5 a6 a7 a8 a9 a10 a11 l(i) 0 2 3 6 6 8 7 7 10 16 14 其中 l(i)=Vl(k) -dut() 06687101614732計算各事件最遲發(fā)生時間Vl和各活動最遲開始時間l的過程求得圖中所有活動的最遲開始時間如下:總結(jié)：求關(guān)鍵路徑步驟1、求Ve(j)2、求Vl(j)3、求e(i)4、求l(i)5、計算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4v1v2v3v5v7v4v6v8v9頂點 Ve Vl0647165714180667168101418

19、a1a2a3a4a5a6a7a8a9a10a11活動 e l l-e Key Activity000022660462583770770710316160141400331、2、3、4、5、算法實現(xiàn)以鄰接表作存儲結(jié)構(gòu)從源點v1出發(fā)，令Ve0=0,按拓?fù)湫蛄星蟾黜旤c的Vej從匯點vn出發(fā)，令Vln-1=Ven-1,按逆拓?fù)湫蛄星笃溆喔黜旤c的Vlj根據(jù)各頂點的Ve和Vl值，計算每條弧的ei和li,找出ei=li的關(guān)鍵活動987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4關(guān)鍵路徑的討論對于AOE網(wǎng)，我們所關(guān)心的有兩個問題：1、完成整個工程的時間可由Ven求得2、關(guān)鍵活動（哪些活動的進(jìn)度是影響整個工程進(jìn)度的關(guān)鍵）在這里可以找到兩條關(guān)鍵路徑：a1、a4、a7、a10a1、a4、a8、a11 它們的路徑長度都是1898