數(shù)據(jù)結(jié)構(gòu)課件：第7章 圖3有向無環(huán)圖及其應(yīng)用

1、圖的連通性問題第7章 圖圖的定義和術(shù)語圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷有向無環(huán)圖及其應(yīng)用最短路徑有向無環(huán)圖7.5 有向無環(huán)圖及其應(yīng)用 有向無環(huán)圖(Directed acycline graph)簡(jiǎn)稱DAG圖，是描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過程的有效工具。v1v2v3v1v2v3有向無環(huán)圖有向圖有向無環(huán)圖7.5 有向無環(huán)圖及其應(yīng)用 對(duì)整個(gè)工程和系統(tǒng)，人們關(guān)心的是兩個(gè)方面的問題：一是工程能否順利進(jìn)行；二是估算整個(gè)工程完成所必須的最短時(shí)間。 有向無環(huán)圖的應(yīng)用：拓?fù)渑判蜿P(guān)鍵路徑有向無環(huán)圖7.5 有向無環(huán)圖及其應(yīng)用 在工程實(shí)踐中，一個(gè)工程項(xiàng)目往往由若干個(gè)子項(xiàng)目組成，這些子項(xiàng)目間往往有多種關(guān)系： 先后關(guān)系，即必須在一子項(xiàng)

2、目完成后，才能開始實(shí)施另一個(gè)子項(xiàng)目； 子項(xiàng)目之間無次序要求，即兩個(gè)子項(xiàng)目可以同時(shí)進(jìn)行，互不影響。兩種常用的活動(dòng)網(wǎng)絡(luò)(Activity Network)7.5 有向無環(huán)圖及其應(yīng)用 AOE網(wǎng)(Activity On Edges)用邊表示活動(dòng)的網(wǎng)絡(luò)AOE網(wǎng)定義：如果在無環(huán)的帶權(quán)有向圖中， 用有向邊表示一個(gè)工程中的活動(dòng)，用邊上權(quán)值表示活動(dòng)持續(xù)時(shí)間，用頂點(diǎn)表示事件，則這樣的有向圖叫做用邊表示活動(dòng)的網(wǎng)絡(luò)，簡(jiǎn)稱 AOE。 AOV網(wǎng)(Activity On Vertices)用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)AOV網(wǎng)定義：若用有向圖表示一個(gè)工程，在圖中用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系。vi 必須先于活動(dòng) vj 進(jìn)行

3、。則這樣的有向圖叫做用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)，簡(jiǎn)稱 AOV。AOV網(wǎng)絡(luò)7.5 有向無環(huán)圖及其應(yīng)用用途：我們經(jīng)常用有向圖來描述一個(gè)工程或系統(tǒng)的進(jìn)行過程。一般來說，一個(gè)工程可以分為若干個(gè)子工程，只要完成了這些子工程，就可以導(dǎo)致整個(gè)工程的完成。例：AOV網(wǎng)絡(luò)若用于教學(xué)計(jì)劃的制定，可以解決：哪些課程是必須先修的，哪些課程是可以并行學(xué)習(xí)的。AOV網(wǎng)絡(luò)7.5 有向無環(huán)圖及其應(yīng)用課程編號(hào)課程名稱先導(dǎo)課程編號(hào)C1程序設(shè)計(jì)基礎(chǔ)無C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1，C2C4匯編語言C1C5算法分析與設(shè)計(jì)C3，C4C6計(jì)算機(jī)組成原理C11C7編譯原理C5，C3C8操作系統(tǒng)C3，C6C9高等數(shù)學(xué)無C10線性代數(shù)C9C11普

4、通物理C9C12數(shù)值分析C9，C10，C1AOV網(wǎng)絡(luò)7.5 有向無環(huán)圖及其應(yīng)用C1C4C2C3C5C9C7C12C10C11C6C8AOV網(wǎng)絡(luò)7.5 有向無環(huán)圖及其應(yīng)用C1C4C2C3C5C9C7C12C10C11C6C8課程編號(hào)課程名稱先導(dǎo)課程編號(hào)C1程序設(shè)計(jì)基礎(chǔ)無C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1，C2C4匯編語言C1C5算法分析與設(shè)計(jì)C3，C4C6計(jì)算機(jī)組成原理C11C7編譯原理C5，C3C8操作系統(tǒng)C3，C6C9高等數(shù)學(xué)無C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C9，C10，C1C1C2C3C4C5C7C9C10C11C6C12C87.5 有向無環(huán)圖及其應(yīng)用C1C9C4C2C1

5、2C10C11C3C5C6C7C8C1拓?fù)湫蛄校篊2C3C4C5C7C9C10C11C6C12C8拓?fù)渑判?.5 有向無環(huán)圖及其應(yīng)用 對(duì)一個(gè)有向無環(huán)圖中的頂點(diǎn)排成一個(gè)具有前后次序的線性序列。拓?fù)渑判蛩惴ǎ褐貜?fù)選擇沒有直接前驅(qū)的頂點(diǎn)。 拓?fù)渑判?.5 有向無環(huán)圖及其應(yīng)用1. 輸入AOV網(wǎng)絡(luò)。令 n 為頂點(diǎn)個(gè)數(shù)。2. 在AOV網(wǎng)絡(luò)中選一個(gè)沒有直接前驅(qū)的頂點(diǎn), 并輸出之; 3. 從圖中刪去該頂點(diǎn), 同時(shí)刪去所有它發(fā)出的有向邊;4. 重復(fù)以上 2、3 步, 直到：全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬桑負(fù)渑判蛲瓿苫蛘?，圖中還有未輸出的頂點(diǎn)，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點(diǎn)，它們都有直接前驅(qū)，再

6、也找不到?jīng)]有前驅(qū)的頂點(diǎn)了。這時(shí)AOV網(wǎng)絡(luò)中必定存在有向環(huán)。拓?fù)渑判?.5 有向無環(huán)圖及其應(yīng)用V1V2V4V3V6V5例：7.5 有向無環(huán)圖及其應(yīng)用G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增設(shè)一個(gè)存放各頂點(diǎn)的入度值的一維數(shù)組 IndegreeV1V2V4V3V6V5021354indegree0.5021230 0 1 2 3 4 57.5 有向無環(huán)圖及其應(yīng)用G.vertices0v1321G.vertices1v2G.vertices2v341G.vertic

7、es3v44G.vertices4v5G.vertices5v643indegree0.5021230 0 1 2 3 4 550sV1V2V4V3V6V50213547.5 有向無環(huán)圖及其應(yīng)用G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643indegree0.5021230 0 1 2 3 4 50s5打印G.vertices5.data4號(hào)和3號(hào)頂點(diǎn)的入度分別減1V1V2V4V3V6V50213547.5 有向無環(huán)圖及其應(yīng)用G.vertices0v1321G.vert

8、ices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643indegree0.5021120 0 1 2 3 4 50sV1V2V4V3V6V50213547.5 有向無環(huán)圖及其應(yīng)用G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643indegree0.5021120 0 1 2 3 4 5 s0打印G.vertices0.data3號(hào)、2號(hào)、1號(hào)頂點(diǎn)的入度分別減1V1V2V4V3V6V50213547.5

9、 有向無環(huán)圖及其應(yīng)用G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643indegree0.5010020 0 1 2 3 4 523sV1V2V4V3V6V50213547.5 有向無環(huán)圖及其應(yīng)用G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643indegree0.5010020 0 1 2 3 4 523sV1V2V4V3V6V50213547.5 有

10、向無環(huán)圖及其應(yīng)用G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643indegree0.5010020 0 1 2 3 4 5 3s2打印G.vertices2.data4號(hào)、1號(hào)頂點(diǎn)的入度分別減1V1V2V4V3V6V50213547.5 有向無環(huán)圖及其應(yīng)用G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643indegree0.5000010 0 1 2

11、3 4 513sV1V2V4V3V6V50213547.5 有向無環(huán)圖及其應(yīng)用G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643indegree0.5000010 0 1 2 3 4 5 3s1打印G.vertices1.dataV1V2V4V3V6V50213547.5 有向無環(huán)圖及其應(yīng)用G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643indegre

12、e0.5000010 0 1 2 3 4 5 3sV1V2V4V3V6V50213547.5 有向無環(huán)圖及其應(yīng)用G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643indegree0.5000010 0 1 2 3 4 5 s3打印G.vertices3.data4號(hào)頂點(diǎn)的入度減1V1V2V4V3V6V50213547.5 有向無環(huán)圖及其應(yīng)用G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices

13、4v5G.vertices5v643indegree0.5000000 0 1 2 3 4 5 4sV1V2V4V3V6V50213547.5 有向無環(huán)圖及其應(yīng)用G.vertices0v131G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643indegree0.5000000 0 1 2 3 4 5 s4打印G.vertices4.data最后輸出的拓?fù)湫蛄袨椋簐6v1v3v2v4v5V1V2V4V3V6V502135427.5 有向無環(huán)圖及其應(yīng)用Status Topological Sort(ALGra

14、ph G)/采用鄰接表存儲(chǔ)結(jié)構(gòu)。若G無回路，則輸出拓?fù)湫蛄胁⒎祷豋K，否則ERROR FindInDegree(G，indegree)； /對(duì)各頂點(diǎn)求入度indegree0.vernum-1 InitStack(S)； /建零入度頂點(diǎn)棧 for(i=0；inextarc) k=padivex；/對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)入度減1 if(！(-indegreek) Push(S，k); /若入度減為0，則入棧 /for /while if(countG.vexnum) return ERROR;/該有向圖有回路 else return OK；/TopologicalSort 關(guān)鍵路徑7.5 有向無環(huán)

15、圖及其應(yīng)用 對(duì)整個(gè)工程和系統(tǒng)，人們關(guān)心的是兩個(gè)方面的問題 (1) 工程能否順利進(jìn)行 對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判?(2) 估算整個(gè)工程完成所必須的最短時(shí)間 對(duì)AOE網(wǎng)求關(guān)鍵路徑AOE網(wǎng)7.5 有向無環(huán)圖及其應(yīng)用AOE網(wǎng)(Activity On Edge Network)：即邊表示活動(dòng)的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無環(huán)圖。其中：頂點(diǎn)表示事件(Event)，弧表示活動(dòng)(Activity)，權(quán)值表示活動(dòng)持續(xù)的時(shí)間。通常可用AOE網(wǎng)來估算工程的完成時(shí)間。AOE網(wǎng)7.5 有向無環(huán)圖及其應(yīng)用v9表示整個(gè)工程的結(jié)束v5表示a4和a5已經(jīng)完成， a7和a8可以開始與每個(gè)活動(dòng)相聯(lián)系的數(shù)是執(zhí)行該活動(dòng)所需的時(shí)間v1表示整

16、個(gè)工程的開始v1v2v3v4v5v6v7v8v9a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a8=7a9=4a10=2AOE網(wǎng)7.5 有向無環(huán)圖及其應(yīng)用上圖AOE網(wǎng)中：共有11項(xiàng)活動(dòng) ：a1, a2, a3, a11；共有9個(gè)事件：v1, v2, v3, v9。每個(gè)事件表示在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)可以開始。v1v2v3v4v5v6v7v8v9a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a8=7a9=4a10=2AOE網(wǎng)7.5 有向無環(huán)圖及其應(yīng)用 由于整個(gè)工程只有一個(gè)開始點(diǎn)和一個(gè)完成點(diǎn)，在正常的情況（無環(huán)）下，網(wǎng)中只有一個(gè)入度為零的點(diǎn)（稱

17、作源點(diǎn)）和一個(gè)出度為零的點(diǎn)（稱作匯點(diǎn)）匯點(diǎn)源點(diǎn)v1v2v3v4v5v6v7v8v9a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a8=7a9=4a10=2AOE網(wǎng)7.5 有向無環(huán)圖及其應(yīng)用依據(jù)AOE-網(wǎng)可以研究什么問題？(1) 完成整項(xiàng)工程至少需要多少時(shí)間？(2) 哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？關(guān)鍵路徑7.5 有向無環(huán)圖及其應(yīng)用 完成工程的最短時(shí)間是從開始點(diǎn)到完成點(diǎn)的最長路徑的長度。路徑長度最長的路徑叫做關(guān)鍵路徑。 從v1到v9的最長路徑是(v1,v2,v5,v8,v9)，路徑長度是18。v1v2v3v4v5v6v7v8v9a1=6a4=1a2=4a3=5a5=1a6=2a

18、7=9a11=4a8=7a9=4a10=2關(guān)鍵路徑7.5 有向無環(huán)圖及其應(yīng)用事件v的最早開始時(shí)間ve(i), 從源點(diǎn)到vi的最長路徑長度?；顒?dòng)ai的最早開始時(shí)間e(i), 等于該活動(dòng)弧尾事件vi的最早開始時(shí)間。 ve(源點(diǎn)) = 0 ； ve(j) = Max ve(i) + dut() e(i) = ve(j)關(guān)鍵路徑7.5 有向無環(huán)圖及其應(yīng)用事件v的最遲開始時(shí)間vl(i)活動(dòng)ai的最遲開始時(shí)間l(i)，這是在不推遲整個(gè)工程完成的前提下，活動(dòng)ai最遲必須開始進(jìn)行的時(shí)間。 vl(匯點(diǎn)) = ve(匯點(diǎn)); vl(i) = Min vl(j) dut() l(i)=vl(k)-dut() 關(guān)鍵路

19、徑算法思想7.5 有向無環(huán)圖及其應(yīng)用1）輸入e條?。╥，j），建立AOE網(wǎng)的存儲(chǔ)結(jié)構(gòu)。2）從源點(diǎn)v0出發(fā)，令ve00按拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最早發(fā)生時(shí)vei（1i n-1）。如果得到的拓?fù)溆行蛐蛄兄许旤c(diǎn)個(gè)數(shù)小于網(wǎng)中頂點(diǎn)數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行步驟（3）。3）從匯點(diǎn)vn出發(fā)，令vln-1= ven-1，按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時(shí)間vli (n-2 i 2)；4）根據(jù)各頂點(diǎn)的ve和vl值，求每條弧s的最早開始時(shí)間e(s)和最遲開始時(shí)間l(s)。若某條弧滿足條件e(s)=l(s)，則為關(guān)鍵活動(dòng)。關(guān)鍵路徑7.5 有向無環(huán)圖及其應(yīng)用v1v2v3v4v5v6v7

20、v8v9a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a8=7a9=4a10=2i012345678備注頂點(diǎn)vv1v2v3v4v5v6v7v8v9最早發(fā)生時(shí)間ve(i) 最遲發(fā)生時(shí)間vl(i)06457716141818141610786600645771614181814161078660關(guān)鍵路徑7.5 有向無環(huán)圖及其應(yīng)用e10=16,v1v2v3v4v5v6v7v8v9a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a8=7a9=4a10=2e1=0,e2=0,e3=0, e4=6,e5=4,e6=5,e7=7,e8=7,e9=7, e11=14, 0

21、645771418181416107866016 l10=16 l1=0 l2=2 l3=3 l4=6 l5=6 l6=8 l7=7 l8=7 l9=10 l11=14關(guān)鍵路徑7.5 有向無環(huán)圖及其應(yīng)用e10=16, l10=16v1v2v3v4v5v6v7v8v9a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a8=7a9=4a10=2e1=0, l1=0e2=0,l2=2e3=0, l3=3e4=6, l4=6e5=4, l5=6e6=5, l6=8e7=7, l7=7e8=7, l8=7e9=7, l9=10e11=14, l11=14關(guān)鍵路徑7.5 有向無環(huán)圖及其應(yīng)用e10=16, l10=16關(guān)鍵路徑7.5 有向無環(huán)圖及其應(yīng)用v1v2v3v4v5v6v7