數(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）先決條件問(wèn)題拓?fù)渑判驅(qū)⒁粋€(gè)有向無(wú)環(huán)圖中所有頂點(diǎn)在不違反先決條件關(guān)系的前提下排成線性序列的過(guò)程稱為拓?fù)渑判驅(qū)W生選修課程問(wèn)題：學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)下列課程，才能無(wú)矛盾、順利地完成學(xué)業(yè)？課程代號(hào)課程名稱 先修課C1程序設(shè)計(jì)基礎(chǔ)無(wú)C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1,C2C4匯編語(yǔ)言C1C5語(yǔ)言的設(shè)計(jì)和分析C3,C4C6計(jì)算機(jī)原理C11C7編譯原理C3.C5C8操作系統(tǒng)C3,C6C9高等數(shù)學(xué)無(wú) C10線性代數(shù)C9C11普通物理C

2、9C12數(shù)值分析C1,C9,C10C1C2C3C4C5C6C7C8C9C10C11C12數(shù)學(xué)模型：有向無(wú)環(huán)圖頂點(diǎn)活動(dòng)（課程）有向弧活動(dòng)i是活動(dòng)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)對(duì)于有向無(wú)環(huán)圖G=(V, E), 所有頂點(diǎn)組成的線性序列如果滿足若在有向無(wú)環(huán)圖G中從頂點(diǎn)Vi到Vj有一條路徑，則在序列中頂點(diǎn)Vi必在頂點(diǎn)Vj之前則該線性序列可稱

3、作一個(gè)拓?fù)湫蛄?。拓?fù)湫蛄胁晃ㄒ?.7 拓?fù)渑判颍ɡm(xù)）任何有向無(wú)環(huán)圖G的所有頂點(diǎn)都可以排在一個(gè)拓?fù)湫蛄欣铩Ｍ負(fù)渑判虻姆椒ㄊ牵?、從圖G中選擇一個(gè)入度為0的頂點(diǎn)并輸出。2、從圖G中刪掉此頂點(diǎn)及其所有的出邊。3、回到第1步繼續(xù)執(zhí)行，直至G所有頂點(diǎn)都被輸出或G中不存在入度為0的頂點(diǎn)。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ù)渑判蛩惴ㄊ紫刃枰?jì)算各頂點(diǎn)的入度，然后在拓?fù)渑判蜻^(guò)程中，當(dāng)某個(gè)頂點(diǎn)的入度為零時(shí)，就將此頂點(diǎn)輸出，同時(shí)將該頂點(diǎn)的所有直接后繼頂點(diǎn)的入度減1。為了避免重復(fù)檢測(cè)入度為零的頂點(diǎn)，設(shè)立一個(gè)棧（或隊(duì)列），以保存當(dāng)前所有“入度為零”的頂點(diǎn)若有向G中所有頂點(diǎn)都被輸出，則表明G中沒(méi)有有向環(huán)，拓?fù)渑判虺晒?。若僅輸出了部分頂點(diǎn)，G中已不存在入度為0的頂點(diǎn)，則表明G中存在有向環(huán)，拓?fù)渑判蚴?。拓?fù)渑判蛩惴▽?shí)現(xiàn)：設(shè)圖G的頂點(diǎn)數(shù)為n1、對(duì)各頂點(diǎn)求入度2、初始化棧S3、把所有入度為0的頂點(diǎn)入棧

6、S4、當(dāng)棧S非空時(shí)循環(huán)4.1 訪問(wèn)棧頂元素v并出棧；4.2 獲得所有與v鄰接的未被訪問(wèn)的頂點(diǎn)w4.3 把w的入度減1；4.4 若w的入度為0則入棧S直至棧S空為止5、如果存在頂點(diǎn)未被訪問(wèn)，則有向圖有環(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(shí)間復(fù)雜度分析關(guān)鍵是，算法在開(kāi)始時(shí)要找出所有入度為0的頂點(diǎn)（同時(shí)可知道其它頂點(diǎn)的

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

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

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

10、？如何計(jì)算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)表示活動(dòng)ai的最早(early)開(kāi)始時(shí)間，是該活動(dòng)的起點(diǎn)所表示事件的最早發(fā)生時(shí)間如果邊表示活動(dòng)ai，則有e(i)=Ve(j)l(i)表示活動(dòng)ai的最遲(last)開(kāi)始時(shí)間，是該活動(dòng)的終點(diǎn)所表示事件的最遲發(fā)生時(shí)間與該活動(dòng)的所需時(shí)間之差如果邊表示活動(dòng)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)表示完成活動(dòng)ai的時(shí)間余量，它是在不增加完成整個(gè)工程所需時(shí)間的情況下，活動(dòng)ai可以拖延的時(shí)間關(guān)鍵活動(dòng)關(guān)鍵路徑上的活動(dòng)，即l(i)=e(i)的活動(dòng)987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9

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

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

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

15、e next778給每個(gè)頂點(diǎn)增加域Id，用于存放事件的入度，給每個(gè)邊增加兩個(gè)域dut和active，用于存放活動(dòng)的持續(xù)時(shí)間和活動(dòng)的編號(hào)。987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4064577161418計(jì)算各事件最早發(fā)生時(shí)間Ve和各活動(dòng)最早開(kāi)始時(shí)間e的過(guò)程棧(底-頂)拓?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 活動(dòng)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ā)生時(shí)間如下: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活動(dòng)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計(jì)算各事件最遲發(fā)生時(shí)間Vl和各活動(dòng)最遲開(kāi)始時(shí)間l的過(guò)程求得圖中所有活動(dòng)的最遲開(kāi)始時(shí)間如下:總結(jié)：求關(guān)鍵路徑步驟1、求Ve(j)2、求Vl(j)3、求e(i)4、求l(i)5、計(jì)算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4v1v2v3v5v7v4v6v8v9頂點(diǎn) Ve Vl0647165714180667168101418

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