圖第五講課件

第七章圖(第五講)有向無環(huán)圖及其應(yīng)用1復(fù)習(xí)回顧最短路徑一、單源最短路徑—Dijkstra（迪杰斯特拉）二、所有頂點(diǎn)間的最短路徑—Floyd（弗洛伊德）2本講內(nèi)容拓?fù)渑判蜿P(guān)鍵路徑3對(duì)工程的活動(dòng)加以抽象：圖中頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)之間的優(yōu)先關(guān)系，這樣的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(ActivityOnVertexNetwork，AOV網(wǎng))。為了描述工程的預(yù)計(jì)進(jìn)度，有時(shí)會(huì)以頂點(diǎn)表示事件,有向邊表示活動(dòng),邊e的權(quán)c(e)表示完成活動(dòng)e所需的時(shí)間(比如天數(shù)),或者說活動(dòng)e持續(xù)時(shí)間，這樣的有向圖為AOE網(wǎng)(ActivityOnEdge)。57.5.1拓?fù)渑判騿栴}1：假設(shè)以有向圖表示一個(gè)工程的施工圖或程序的流程圖，則程序中能否出現(xiàn)回路？問題2：如何檢查有向圖中是否存在回路？問題3：何謂拓?fù)渑判颍?拓?fù)渑判蛲負(fù)渑判颍河赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱為拓?fù)渑判颉?/p>

(a)偏序(b)全序ADCBADCB7拓?fù)渑判蚝沃^拓?fù)渑判?

換句話說：對(duì)有向圖進(jìn)行如下操作，按照有向圖給出的次序關(guān)系，將圖中的頂點(diǎn)排成一個(gè)線性序列，對(duì)于沒有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。問題4：如何進(jìn)行拓?fù)渑判颍?拓?fù)渑判蚍椒ǎ?1)從入度為0的頂點(diǎn)（如v0）開始；

(2)輸出v0，將與之相關(guān)聯(lián)的尾端弧刪除；

(3)重復(fù)上述兩步，直至圖中全部頂點(diǎn)已輸出，或不存在無前驅(qū)頂點(diǎn)為止。

前一種情況說明有向圖中不存在環(huán)，后一種情況則說明有向圖中存在環(huán)。

檢測(cè)一個(gè)有向圖是否存在回路的方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若圖中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校瑒t該圖中必定不存在環(huán)。100

0

12

4

5

3

0

12

4

5

3

41253全部可能的拓?fù)渑判蛐蛄校?41253041523045123450123401253405123401523問題5：有向圖的拓?fù)溆行蛐蛄惺欠裎ㄒ唬?1拓?fù)渑判驅(qū)崿F(xiàn)拓?fù)渑判虻乃惴ɑA(chǔ)

存儲(chǔ)結(jié)構(gòu):假設(shè)有向圖以鄰接表的形式存儲(chǔ)操作過程:將所有入度為0的頂點(diǎn)入棧；

當(dāng)棧非空時(shí)重復(fù)執(zhí)行下列操作：從棧中退出頂點(diǎn)k；（1）將k頂點(diǎn)的信息輸出；（2）將與k鄰接的所有頂點(diǎn)的入度減1。13

StatusTopologicalSort(ALGraphG){//有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。若G無回路,則輸出G的頂點(diǎn)的一個(gè)拓?fù)?/p>

//序列并返回OK,//否則返回ERRORinti,k,count,indegree[MAX_VERTEX_NUM];SqStackS;ArcNode*p;FindInDegree(G,indegree);//對(duì)各頂點(diǎn)求入度indegree[0..vernum-1]InitStack(S);//初始化棧

for(i=0;i<G.vexnum;++i)//建零入度頂點(diǎn)棧Sif(!indegree[i])Push(S,i);//入度為0者進(jìn)棧

count=0;//對(duì)輸出頂點(diǎn)計(jì)數(shù)

while(!StackEmpty(S)){//棧不空

Pop(S,i);

14

printf("%s",G.vertices[i].data);//輸出i號(hào)頂點(diǎn)并計(jì)數(shù)

++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){//對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1k=p->adjvex;if(!(--indegree[k]))//若入度減為0,則入棧

Push(S,k);}}if(count<G.vexnum){printf("此有向圖有回路\n");returnERROR;}else{printf("為一個(gè)拓?fù)湫蛄小n");returnOK;}}15拓?fù)渑判虼鎯?chǔ)結(jié)構(gòu)示例:C0C1C2C3C4C5

C0C1C2C30C4C50degreedataadj

130103

1

vexlink

30

5

1

50

0

1

5017拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度分析

如果給定的有向圖有n個(gè)頂點(diǎn)和e條邊，那么求各頂點(diǎn)入度的時(shí)間為O（e），在拓?fù)渑判虻倪^程中，查找入度為零的頂點(diǎn)的時(shí)間為O（n），頂點(diǎn)進(jìn)棧及退棧輸出共執(zhí)行n次，入度減1的操作執(zhí)行e次，所以，總的執(zhí)行時(shí)間為O（n+e）。18

用有向邊表示活動(dòng),邊e的權(quán)c(e)表示完成活動(dòng)e所需的時(shí)間(比如天數(shù)),或者說活動(dòng)e持續(xù)時(shí)間，這樣的有向圖為AOE網(wǎng)(ActivityOnEdge)。

7.5.2AOE網(wǎng)與關(guān)鍵路徑

而這樣的網(wǎng)，是能夠用來估計(jì)工程的完成時(shí)間，并能找出影響工程進(jìn)度的“關(guān)鍵活動(dòng)”，從而可為決策者提供修改各活動(dòng)的預(yù)計(jì)進(jìn)度的依據(jù)。19vi+1vi+3vi+2vivi+4vi+5a1=13a3=12a4=6a2=5前趨活動(dòng)后繼活動(dòng)a5=6

相關(guān)術(shù)語21

幾個(gè)定義：

(1)事件v的最早可發(fā)生時(shí)間：假設(shè)事件x是源點(diǎn),事件y為匯點(diǎn),并規(guī)定事件x的發(fā)生時(shí)間為0。定義圖中任一事件v的最早(eventearly)可發(fā)生時(shí)間ve(v)等于x到v所有路徑長度的最大值,即：ve(v)=

上式中的MAX是對(duì)x到v的所有路徑p取最大值,c(p)表示路徑p的長度(路徑上邊長之和),即：c(p)=

完成整個(gè)工程所需的最少時(shí)間,等于事件y的最早可發(fā)生時(shí)間ve(y)。22v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2

源點(diǎn)匯點(diǎn)23

(2)事件v的最遲可發(fā)生時(shí)間：定義在不影響整個(gè)工程進(jìn)度的前提下,事件v必須發(fā)生的時(shí)間稱為v的最遲(eventlate)可發(fā)生時(shí)間,記作vl(v)。vl(v)應(yīng)等于ve(y)與v到y(tǒ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=<v,w>。對(duì)關(guān)鍵活動(dòng)來說,不存在富余時(shí)間。顯然,關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(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è)工程的工期。25ve(v)最早開始時(shí)間ve(v)最遲開始時(shí)間v000v139v21010v31223v42222v51717v62031v72828v8333326

(5)按頂點(diǎn)拓?fù)浯涡蛑嫘?反復(fù)用公式,依次求其余各項(xiàng)點(diǎn)v的vl(v)的值。

(6)活動(dòng)ai的最早開始時(shí)間e(i)是該活動(dòng)的起點(diǎn)所表示的事件最早發(fā)生時(shí)間。如果由邊<vj,vk>表示活動(dòng)ai,則有e(i)=ve(j)。

(7)活動(dòng)ai的最遲開始時(shí)間l(i)是該活動(dòng)的終點(diǎn)所表示事件的最遲發(fā)生時(shí)間與該活動(dòng)的所需時(shí)間之差。如果用邊<vj,vk>表示活動(dòng)ai,則有l(wèi)(i)=vl(k)-ai所需時(shí)間。29

(8)一個(gè)活動(dòng)ai的最遲開始時(shí)間l(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í),說明該活動(dòng)必須如期完成,否則就會(huì)拖延完成整個(gè)工程的進(jìn)度。所以我們稱l(i)-e(i)=0,即l(i)=e(i)的活動(dòng)ai是關(guān)鍵活動(dòng)。30計(jì)算各事件的ve(v)如下：ve(A)=0,ve(B)=ve(A)+c(a1)=6ve(C)=ve(A)+c(a2)=4ve(D)=ve(A)+c(a3)=5ve(E)=max(ve(B)+c(a4),ve(C)+c(a5)}=max{7,5}=731ve(F)=ve(E)+c(a7)=16ve(G)=ve(E)+c(a8)=14ve(H)=ve(D)+c(a6)=7ve(I)=max{ve(F)+c(a10),ve(G)+c(a11),ve(H)+c(a9)}=max(18,18,11}=1832計(jì)算各事件的vl(v)如下：

vl(I)=ve(I)=18vl(F)=vl(I)-c(a10)=16vl(G)=vl(I)-c(a11)=14vl(H)=vl(I)-c(a9)=1433

vl(E)=min(vl(F)-c(a7),vl(G)-c(a8)}={7,7}=7vl(D)=vl(H)-c(a6)=12vl(C)=vl(E)-c(a5)=6vl(B)=vl(E)-c(a4)=6vl(A)=min(vl(B)-c(a1),vl(C)-c(a2),vl(D)-c(a3)}={0,2,7}=034計(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(C)=4,l(5)=vl(E)-1=6,d(5)=235活動(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)=036由此可知,關(guān)鍵活動(dòng)有a11、a10、a8、a7、a4、a1,因此關(guān)鍵路徑有兩條：A-B-E-F-I和A-B-E-G-I。37v0v5v4v7v3v2v1v6v8a1=5a2=6a3=3a8=5a4=12a5=3a10=4a9=1a12=5a11=4a6=3a7=3a13=2v9a14=2假設(shè)一個(gè)工程的進(jìn)度計(jì)劃用AOE網(wǎng)表示，如圖所示。①求出每個(gè)事件的最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間。②該工程完