第7章 圖(第五講).ppt

1、1,第七章 圖(第五講),有向無(wú)環(huán)圖及其應(yīng)用,2,復(fù)習(xí)回顧,最短路徑,一、單源最短路徑Dijkstra（迪杰斯特拉） 二、所有頂點(diǎn)間的最短路徑Floyd（弗洛伊德）,3,本講內(nèi)容,拓?fù)渑判?關(guān)鍵路徑,4,7.5 有向無(wú)環(huán)圖及其應(yīng)用,有向無(wú)環(huán)圖(Directed Acycling Graph)：是圖中沒(méi)有回路(環(huán))的有向圖。是一類(lèi)具有代表性的圖，主要用于研究工程項(xiàng)目的工序問(wèn)題、工程時(shí)間進(jìn)度問(wèn)題等。 一個(gè)工程(project)都可分為若干個(gè)稱為活動(dòng)(active)的子工程(或工序)，各個(gè)子工程受到一定的條件約束：某個(gè)子工程必須開(kāi)始于另一個(gè)子工程完成之后；整個(gè)工程有一個(gè)開(kāi)始點(diǎn)(起點(diǎn))和一個(gè)終點(diǎn)。人們

2、關(guān)心： 工程能否順利完成?影響工程的關(guān)鍵活動(dòng)是什么? 估算整個(gè)工程完成所必須的最短時(shí)間是多少?,5,對(duì)工程的活動(dòng)加以抽象：圖中頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)之間的優(yōu)先關(guān)系，這樣的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(Activity On Vertex Network ，AOV網(wǎng))。,為了描述工程的預(yù)計(jì)進(jìn)度，有時(shí)會(huì)以頂點(diǎn)表示事件,有向邊表示活動(dòng),邊e的權(quán)c(e)表示完成活動(dòng)e所需的時(shí)間(比如天數(shù)),或者說(shuō)活動(dòng)e持續(xù)時(shí)間，這樣的有向圖為AOE網(wǎng)(Activity On Edge)。,6,7.5.1 拓?fù)渑判?問(wèn)題1：假設(shè)以有向圖表示一個(gè)工程的施工 圖或程序的流程圖，則程序中能否 出現(xiàn)回路？ 問(wèn)題2：如何檢查

3、有向圖中是否存在回路？ 問(wèn)題3：何謂拓?fù)渑判颍?7,拓?fù)渑判?拓?fù)渑判颍河赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱為拓?fù)渑判颉?(a)偏序 (b)全序,8,B,D,A,C,對(duì)于下列有向圖,不能求得它的拓?fù)溆行蛐蛄小?因?yàn)閳D中存在一個(gè)回路 B, C, D,9,拓?fù)渑判?何謂拓?fù)渑判? 換句話說(shuō)：對(duì)有向圖進(jìn)行如下操作，按照有向圖給出的次序關(guān)系，將圖中的頂點(diǎn)排成一個(gè)線性序列，對(duì)于沒(méi)有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。,問(wèn)題4：如何進(jìn)行拓?fù)渑判颍?10,拓?fù)渑判?方法： (1)從入度為0的頂點(diǎn)（如v0）開(kāi)始； (2)輸出v0，將與之相關(guān)聯(lián)的尾端弧刪除； (3)重復(fù)上述兩步

4、，直至圖中全部頂點(diǎn)已輸出，或不存在無(wú)前驅(qū)頂點(diǎn)為止。 前一種情況說(shuō)明有向圖中不存在環(huán)，后一種情況則說(shuō)明有向圖中存在環(huán)。,檢測(cè)一個(gè)有向圖是否存在回路的方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若圖中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該圖中必定不存在環(huán)。,11,0,0,1,2,4,5,3,4,1,2,5,3,全部可能的拓?fù)渑判蛐蛄校?041253 041523 045123 450123 401253 405123 401523,問(wèn)題5：有向圖的拓?fù)溆行蛐蛄惺欠裎ㄒ唬?12,拓?fù)渑判?分析： （1）拓?fù)渑判蜃铌P(guān)鍵的操作是什么？ （2）圖的存儲(chǔ)結(jié)構(gòu)？ （3）如何處理多個(gè)入度為0的頂點(diǎn)？,問(wèn)題6：如何在計(jì)

5、算機(jī)內(nèi)實(shí)現(xiàn)有向圖的拓?fù)渑判颍?13,拓?fù)渑判?實(shí)現(xiàn)拓?fù)渑判虻乃惴ɑA(chǔ) 存儲(chǔ)結(jié)構(gòu):假設(shè)有向圖以鄰接表的形式存儲(chǔ) 操作過(guò)程: 將所有入度為0的頂點(diǎn)入棧； 當(dāng)棧非空時(shí)重復(fù)執(zhí)行下列操作： 從棧中退出頂點(diǎn)k； （1）將k頂點(diǎn)的信息輸出； （2）將與k鄰接的所有頂點(diǎn)的入度減1。,14,Status TopologicalSort(ALGraph G) / 有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。若G無(wú)回路,則輸出G的頂點(diǎn)的一個(gè)拓?fù)?/序列并返回OK, / 否則返回ERROR int i,k,count,indegreeMAX_VERTEX_NUM; SqStack S; ArcNode *p; FindInDegre

6、e(G,indegree); / 對(duì)各頂點(diǎn)求入度indegree0.vernum-1 InitStack(S); / 初始化棧 for(i=0;iG.vexnum;+i) / 建零入度頂點(diǎn)棧S if(!indegreei) Push(S,i); / 入度為0者進(jìn)棧 count=0; / 對(duì)輸出頂點(diǎn)計(jì)數(shù) while(!StackEmpty(S) / 棧不空 Pop(S,i);,15,printf(%s ,G.verticesi.data); / 輸出i號(hào)頂點(diǎn)并計(jì)數(shù) +count; for(p=G.verticesi.firstarc;p;p=p-nextarc) / 對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度

7、減1 k=p-adjvex; if(!(-indegreek) / 若入度減為0,則入棧 Push(S,k); if(countG.vexnum) printf(此有向圖有回路n); return ERROR; else printf(為一個(gè)拓?fù)湫蛄?。n); return OK; ,16,void FindInDegree(ALGraph G,int indegree) / 求頂點(diǎn)的入度 int i; ArcNode *p; for(i=0;iadjvex+; p=p-nextarc; ,17,拓?fù)渑判虼鎯?chǔ)結(jié)構(gòu)示例:,18,拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度分析,如果給定的有向圖有n個(gè)頂點(diǎn)和e條邊，那么

8、求各頂點(diǎn)入度的時(shí)間為O（e），在拓?fù)渑判虻倪^(guò)程中，查找入度為零的頂點(diǎn)的時(shí)間為O（n），頂點(diǎn)進(jìn)棧及退棧輸出共執(zhí)行n次，入度減1的操作執(zhí)行e次，所以，總的執(zhí)行時(shí)間為O（n+e）。,19,用有向邊表示活動(dòng),邊e的權(quán)c(e)表示完成活動(dòng)e所需的時(shí)間(比如天數(shù)),或者說(shuō)活動(dòng)e持續(xù)時(shí)間，這樣的有向圖為AOE網(wǎng)(Activity On Edge)。,7.5.2 AOE網(wǎng)與關(guān)鍵路徑,而這樣的網(wǎng)，是能夠用來(lái)估計(jì)工程的完成時(shí)間，并能找出影響工程進(jìn)度的“關(guān)鍵活動(dòng)”，從而可為決策者提供修改各活動(dòng)的預(yù)計(jì)進(jìn)度的依據(jù)。,20,源點(diǎn),匯點(diǎn),AOE網(wǎng)示例,那么如何利用這樣的圖計(jì)算完成工程 的最少所需時(shí)間呢？又如何找出影響 工程

9、進(jìn)度的關(guān)鍵活動(dòng)呢？,21,vi+1,vi+3,vi+2,vi,vi+4,vi+5,前趨活動(dòng),后繼活動(dòng),相關(guān)術(shù)語(yǔ),22,幾個(gè)定義： (1) 事件v的最早可發(fā)生時(shí)間：假設(shè)事件x是源點(diǎn),事件y為匯點(diǎn),并規(guī)定事件x的發(fā)生時(shí)間為0。定義圖中任一事件v的最早(event early)可發(fā)生時(shí)間ve(v)等于x到v所有路徑長(zhǎng)度的最大值,即：,ve(v)=,上式中的MAX是對(duì)x到v的所有路徑p取最大值,c(p)表示路徑p的長(zhǎng)度(路徑上邊長(zhǎng)之和) ,即：,c(p)=,完成整個(gè)工程所需的最少時(shí)間,等于事件y的最早可發(fā)生時(shí)間ve(y)。,23,源點(diǎn),匯點(diǎn),24,整個(gè)工程完成的最短時(shí)間指的是：從有向圖的源點(diǎn)到匯點(diǎn)的最

10、長(zhǎng)路徑的長(zhǎng)度，具有最大長(zhǎng)度的路徑叫關(guān)鍵路徑。,“關(guān)鍵活動(dòng)”指的是：該弧上的權(quán)值增加將使有向圖上的最長(zhǎng)路徑的長(zhǎng)度增加。 注意：在一個(gè)AOE網(wǎng)中，可以有不止一條的關(guān)鍵路徑。,源點(diǎn),匯點(diǎn),25,(2) 事件v的最遲可發(fā)生時(shí)間：定義在不影響整個(gè)工程進(jìn)度的前提下,事件v必須發(fā)生的時(shí)間稱為v的最遲(event late)可發(fā)生時(shí)間,記作vl(v)。vl(v)應(yīng)等于ve(y)與v到y(tǒng)的最長(zhǎng)路徑長(zhǎng)度之差(y是匯點(diǎn)),即：,vl(v)=ve(y) -,(3) 關(guān)鍵活動(dòng):若活動(dòng)v滿足ve(v)+c(ai)=vl(w),則稱活動(dòng)ai為關(guān)鍵活動(dòng)，ai=。 對(duì)關(guān)鍵活動(dòng)來(lái)說(shuō),不存在富余時(shí)間。顯然,關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵

11、活動(dòng)。找出關(guān)鍵活動(dòng)的意義在于,可以適當(dāng)?shù)卦黾訉?duì)關(guān)鍵活動(dòng)的投資(人力、物力等),相應(yīng)地減少對(duì)非關(guān)鍵活動(dòng)的投資,從而減少關(guān)鍵活動(dòng)的持續(xù)時(shí)間,縮短整個(gè)工程的工期。,26,27,只要計(jì)算出各項(xiàng)點(diǎn)的ve(v)和vl(v)的值,就能找出所有的關(guān)鍵活動(dòng)。為了便于計(jì)算,引入下面兩個(gè)遞推式,其中,x和y分別是源點(diǎn)和匯點(diǎn)。 ve(x)=0 ve(w)= wx 上式中的MAX對(duì)所有射入w的邊取最大值。 vl(y)=0 vl(v)= vy,28,(1) 對(duì)于源點(diǎn)x,置ve(x)=0； (2) 對(duì)AOE網(wǎng)進(jìn)行拓?fù)渑判?。如發(fā)現(xiàn)回路,工程無(wú)法進(jìn)行,則退出；否則繼續(xù)下一步。 (3) 按頂點(diǎn)的拓?fù)浯涡?反復(fù)用遞推公式,依次求其

12、余各項(xiàng)點(diǎn)v的ve(v)值。(實(shí)際上,步驟(2)和步驟(3)可以合在一起完成,即一邊對(duì)頂點(diǎn)進(jìn)行拓?fù)渑判?一邊求出各點(diǎn)的ve(v)之值。) (4) 對(duì)于匯點(diǎn)y,置vl(y)=ve(y)；,求AOE網(wǎng)的關(guān)鍵活動(dòng)的過(guò)程,29,(5) 按頂點(diǎn)拓?fù)浯涡蛑嫘?反復(fù)用公式,依次求其余各項(xiàng)點(diǎn)v的vl(v)的值。 (6) 活動(dòng)ai的最早開(kāi)始時(shí)間e(i)是該活動(dòng)的起點(diǎn)所表示的事件最早發(fā)生時(shí)間。如果由邊表示活動(dòng)ai,則有e(i)=ve(j)。 (7) 活動(dòng)ai的最遲開(kāi)始時(shí)間l(i)是該活動(dòng)的終點(diǎn)所表示事件的最遲發(fā)生時(shí)間與該活動(dòng)的所需時(shí)間之差。如果用邊表示活動(dòng)ai,則有l(wèi)(i)=vl(k)-ai所需時(shí)間。,30,(8

13、) 一個(gè)活動(dòng)ai的最遲開(kāi)始時(shí)間l(i)和其最早開(kāi)始時(shí)間e(i)的差額d(i)=l(i)-e(i)是該活動(dòng)完成的時(shí)間余量(富余時(shí)間)。它是在不增加完成整個(gè)工程所需的總時(shí)間的情況下,活動(dòng)ai可以拖延的時(shí)間。 (9) 當(dāng)一活動(dòng)的時(shí)間余量為零時(shí),說(shuō)明該活動(dòng)必須如期完成,否則就會(huì)拖延完成整個(gè)工程的進(jìn)度。所以我們稱l(i)-e(i)=0,即l(i)=e(i)的活動(dòng)ai是關(guān)鍵活動(dòng)。,31,計(jì)算各事件的ve(v)如下： ve(A)=0,ve(B)=ve(A)+c(a1)=6 ve(C)=ve(A)+c(a2)=4 ve(D)=ve(A)+c(a3)=5 ve(E)=max(ve(B)+c(a4),ve(C)+

14、c(a5)=max7,5=7,32,ve(F)=ve(E)+c(a7)=16 ve(G)=ve(E)+c(a8)=14 ve(H)=ve(D)+c(a6)=7 ve(I)=maxve(F)+c(a10),ve(G)+c(a11),ve(H)+c(a9) =max(18,18,11=18,33,計(jì)算各事件的vl(v)如下： vl(I)=ve(I)=18 vl(F)=vl(I)-c(a10)=16 vl(G)=vl(I)-c(a11)=14 vl(H)=vl(I)-c(a9)=14,34,vl(E)=min(vl(F)-c(a7),vl(G)-c(a8)=7,7=7 vl(D)=vl(H)-c(a

15、6)=12 vl(C)=vl(E)-c(a5)=6 vl(B)=vl(E)-c(a4)=6 vl(A)=min(vl(B)-c(a1),vl(C)-c(a2),vl(D)-c(a3)=0,2,7=0,35,計(jì)算各活動(dòng)的e(a)、l(a)和d(a)如下： 活動(dòng)a1：e(1)=ve(A)=0,l(1)=vl(B)-6=0,d(1)=0 活動(dòng)a2：e(2)=ve(A)=0,l(2)=vl(C)-4=2,d(2)=2 活動(dòng)a3：e(3)=ve(A)=0,l(3)=vl(D)-5=7,d(3)=7 活動(dòng)a4：e(4)=ve(B)=6,l(4)=vl(E)-1=6,d(4)=0 活動(dòng)a5：e(5)=ve(

16、C)=4,l(5)=vl(E)-1=6,d(5)=2,36,活動(dòng)a6：e(6)=ve(D)=5,l(6)=vl(H)-2=12,d(6)=7 活動(dòng)a7：e(7)=ve(E)=7,l(7)=vl(F)-9=7,d(7)=0 活動(dòng)a8：e(8)=ve(E)=7,l(8)=vl(G)-7=7,d(8)=0 活動(dòng)a9：e(9)=ve(H)=7,l(9)=vl(G)-4=10,d(9)=3 活動(dòng)a10：e(10)=ve(F)=16,l(10)=vl(I)-2=16,d(10)=0 活動(dòng)a11：e(11)=ve(G)=14,l(11)=vl(I)-4=14,d(11)=0,37,由此可知,關(guān)鍵活動(dòng)有a11、a10、a8、a7、a4、a1,因此關(guān)鍵路徑有兩條：A-B-E-F-I和A-B-E-G-I。,38,假設(shè)一個(gè)工程的進(jìn)度計(jì)劃用AOE網(wǎng)表示，如圖所示。 求出每個(gè)