有向無環(huán)圖無環(huán)的有向圖稱為有向無環(huán)圖，簡(jiǎn)稱DAG圖P179圖7.21：有向樹、DAG圖、有向圖DAG圖可用于：描畫含有公共子式的表達(dá)式；描畫工程的進(jìn)展過程；有向無環(huán)圖是描畫一項(xiàng)工程進(jìn)展過程的有效工具，主要進(jìn)展拓?fù)渑判蚝完P(guān)鍵途徑的操作。工程能否順利進(jìn)展—拓?fù)渑判蛲瓿烧麄€(gè)工程所需的最短時(shí)間—關(guān)鍵途徑活動(dòng)網(wǎng)絡(luò)(ActivityNetwork)方案、施工過程、消費(fèi)流程、程序流程等都是“工程〞。除了很小的工程外，普通都可以將工程分為假設(shè)干個(gè)稱作“活動(dòng)〞的子工程，完成了這些活動(dòng)，整個(gè)工程就可以完成了。例：計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門課程的學(xué)習(xí)就是整個(gè)工程的一個(gè)活動(dòng)，其中有些課程要求先修課程，有些那么不要求，這樣在有的課程之間就存在領(lǐng)先關(guān)系，而有的課程那么可以并行學(xué)習(xí)。用頂點(diǎn)表示活動(dòng)的網(wǎng)(AOV-網(wǎng))可以用有向圖表示一個(gè)工程。在這種有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊<Vi,Vj>表示活動(dòng)Vi必需先于活動(dòng)Vj進(jìn)展。這種有向圖稱作頂點(diǎn)表示活動(dòng)的AOV網(wǎng)(ActivityOnVertex)。在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路,即有向環(huán)。假設(shè)出現(xiàn)了有向環(huán)，那么意味著某項(xiàng)活動(dòng)應(yīng)以本人作為先決條件。因此，對(duì)給定的AOV網(wǎng)絡(luò)，必需先判別它能否存在有向環(huán)。檢測(cè)有向環(huán)的一種方法是對(duì)AOV網(wǎng)絡(luò)構(gòu)造它的拓?fù)溆行蛐蛄?。即將各個(gè)頂點(diǎn)(代表各個(gè)活動(dòng))陳列成一個(gè)線性有序的序列，使得AOV網(wǎng)絡(luò)中一切應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算就叫做拓?fù)渑判颉＜僭O(shè)經(jīng)過拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的一切頂點(diǎn)都排入一個(gè)拓?fù)溆行虻男蛄兄?那么該網(wǎng)絡(luò)中必定不會(huì)出現(xiàn)有向環(huán)。假設(shè)AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。例如,對(duì)學(xué)生課程學(xué)習(xí)工程圖進(jìn)展拓?fù)渑判?得到的拓?fù)溆行蛐蛄袨镃1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C2拓?fù)渑判虻姆椒á佥斎階OV網(wǎng)絡(luò)，令n為頂點(diǎn)個(gè)數(shù)。 ②在AOV網(wǎng)絡(luò)中選一個(gè)沒有直接前驅(qū)的頂點(diǎn),并輸出之;③從圖中刪去該頂點(diǎn),同時(shí)刪去一切它發(fā)出的有向邊;④反復(fù)以上②、③步,直到全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄袠?gòu)成，拓?fù)渑判蛲瓿桑换驁D中還有未輸出的頂點(diǎn),但已跳出處置循環(huán)。闡明圖中還剩下一些頂點(diǎn),它們都有直接前驅(qū)。這時(shí)網(wǎng)絡(luò)中必存在有向環(huán)。C0C1C2C3C4C5拓?fù)渑判虻倪^程(a)有向無環(huán)圖C2C5C1C0C3(b)輸出頂點(diǎn)C4C1C2C5C3(c)輸出頂點(diǎn)C0C4C0C2C5C1C3(d)輸出頂點(diǎn)C3C1C2C5(e)輸出頂點(diǎn)C2C5C1(f)輸出頂點(diǎn)C1C5(g)輸出頂點(diǎn)C5最后得到的拓?fù)溆行蛐蛄袨镃4,C0,C3,C2,C1,C5。它滿足圖中給出的一切前驅(qū)和后繼關(guān)系，對(duì)于本來沒有這種關(guān)系的頂點(diǎn)，如C4和C2，也排出了先后次序關(guān)系。(h)拓?fù)渑判蛲瓿沙撕苄〉墓こ掏?，普通都可以將工程分為假設(shè)干個(gè)稱作“活動(dòng)〞的子工程，完成了這些活動(dòng)，整個(gè)工程就可以完成了。是從源點(diǎn)V0到頂點(diǎn)Vi的最長(zhǎng)途徑長(zhǎng)度08122228404658例如,以下圖就是一個(gè)AOE網(wǎng)。假設(shè)輸出頂點(diǎn)個(gè)數(shù)少于AOV網(wǎng)絡(luò)的頂點(diǎn)個(gè)數(shù),那么報(bào)告網(wǎng)絡(luò)中存在有向環(huán)。表示活動(dòng)ak的最早能夠開場(chǎng)時(shí)間和最遲允許開場(chǎng)時(shí)間的時(shí)間余量。其中,dur(<i,j>)是完成ak所需的時(shí)間。假設(shè)出現(xiàn)了有向環(huán)，那么意味著某項(xiàng)活動(dòng)應(yīng)以本人作為先決條件。用頂點(diǎn)表示活動(dòng)的網(wǎng)(AOV-網(wǎng))全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄袠?gòu)成，拓?fù)渑判蛲瓿?；indegreedataadjl[k]=vl[j]-dur(<i,j>)。這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算就叫做拓?fù)渑判?。最后得到的拓?fù)溆行蛐蛄袨镃4,C0,C3,C2,C1,C5。假設(shè)AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。AOV網(wǎng)絡(luò)及其鄰接表表示C0C1C2C3C4C5C0C1C2C30C4C50012345indegreedataadj1301031destlink3051500150拓?fù)渑判蛩惴擅璁嬋缦拢航⑷攵葹榱愕捻旤c(diǎn)棧;當(dāng)入度為零的頂點(diǎn)棧不空時(shí),反復(fù)執(zhí)行從頂點(diǎn)棧中退出一個(gè)頂點(diǎn),并輸出之;從AOV網(wǎng)絡(luò)中刪去這個(gè)頂點(diǎn)和它發(fā)出的邊,邊的終頂點(diǎn)入度減一;假設(shè)邊的終頂點(diǎn)入度減至0,那么該頂點(diǎn)進(jìn)入度為零的頂點(diǎn)棧;假設(shè)輸出頂點(diǎn)個(gè)數(shù)少于AOV網(wǎng)絡(luò)的頂點(diǎn)個(gè)數(shù),那么報(bào)告網(wǎng)絡(luò)中存在有向環(huán)。P182算法7.12用邊表示活動(dòng)的網(wǎng)絡(luò)(AOE網(wǎng))假設(shè)在帶權(quán)的有向無環(huán)圖中,用有向邊表示一個(gè)工程中的活動(dòng)(Activity),用邊上權(quán)值表示活動(dòng)繼續(xù)時(shí)間(Duration),用頂點(diǎn)表示事件(Event),那么這樣的有向圖叫做用邊表示活動(dòng)的網(wǎng)絡(luò),簡(jiǎn)稱AOE(ActivityOnEdges)網(wǎng)。AOE網(wǎng)在某些工程進(jìn)度估算方面非常有用。例如，可以使人們了解：完成整個(gè)工程至少需求多少時(shí)間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?為縮短完成工程所需的時(shí)間,該當(dāng)加快哪些活動(dòng)? 從源點(diǎn)到各個(gè)頂點(diǎn),以及從源點(diǎn)到匯點(diǎn)的有向途徑能夠不止一條，這些途徑的長(zhǎng)度也能夠不同，完成不同途徑的活動(dòng)所需的時(shí)間雖然不同，但只需各條途徑上一切活動(dòng)都完成了,整個(gè)工程才干完成。因此,完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)途徑長(zhǎng)度,即在這條途徑上一切活動(dòng)的繼續(xù)時(shí)間之和。這條途徑長(zhǎng)度最長(zhǎng)的途徑叫做關(guān)鍵途徑(CriticalPath)。a9=61324a1=8a2=125678a10=12a8=18a5=28a6=8a7=6a3=14a4=10要找出關(guān)鍵途徑，必需找出關(guān)鍵活動(dòng),即不按期完成就會(huì)影響整個(gè)工程完成的活動(dòng)。關(guān)鍵途徑上的一切活動(dòng)都是關(guān)鍵活動(dòng)。因此,只需找到了關(guān)鍵活動(dòng),就可以找到關(guān)鍵途徑。例如,以下圖就是一個(gè)AOE網(wǎng)。定義幾個(gè)與計(jì)算關(guān)鍵活動(dòng)有關(guān)的量：①事件Vi的最早發(fā)生時(shí)間ve(i)是從源點(diǎn)V0到頂點(diǎn)Vi的最長(zhǎng)途徑長(zhǎng)度②事件Vi的最遲發(fā)生時(shí)間vl[i]是在保證匯點(diǎn)Vn-1在ve[n-1]時(shí)辰完成〔即不影響整個(gè)工程工期〕的前提下，事件Vi允許的最遲開場(chǎng)時(shí)間。③活動(dòng)ak的最早能夠開場(chǎng)時(shí)間e[k]設(shè)活動(dòng)ak在弧<Vi,Vj>上,那么e[k]是從源點(diǎn)V0到頂點(diǎn)Vi的最長(zhǎng)途徑長(zhǎng)度。因此,e[k]=ve[i]④活動(dòng)ak的最遲允許開場(chǎng)時(shí)間l[k]在不會(huì)引起整個(gè)工程時(shí)間延誤的前提下,該活動(dòng)允許的最遲開場(chǎng)時(shí)間。l[k]=vl[j]-dur(<i,j>)。其中,dur(<i,j>)是完成ak所需的時(shí)間。⑤時(shí)間余量l[k]-e[k]表示活動(dòng)ak的最早能夠開場(chǎng)時(shí)間和最遲允許開場(chǎng)時(shí)間的時(shí)間余量。l[k]==e[k]表示活動(dòng)ak是沒有時(shí)間余量的關(guān)鍵活動(dòng)。為找出關(guān)鍵活動(dòng),需求求出各個(gè)活動(dòng)的e[k]與l[k]，以判別能否l[k]==e[k]。為求得e[k]與l[k],需求先求得從源點(diǎn)V0到各個(gè)頂點(diǎn)Vi的ve[i]和vl[i]。求ve[i]和vl[i]的遞推公式從ve[0]=0開場(chǎng)，向前遞推<Vj,Vi>S2,i=1,2,,n-1S2是一切指向Vi的有向邊<Vj,Vi>的集合。從vl[n-1]=ve[n-1]開場(chǎng)，反向遞推<Vi,Vj>S1,i=n-2,n-3,,0S1是一切源自Vi的有向邊<Vi,Vj>的集合。這兩個(gè)遞推公式的計(jì)算必需分別在拓?fù)溆行蚣澳嫱負(fù)溆行虻那疤嵯逻M(jìn)展。設(shè)活動(dòng)ak(k=1,2,…,e)在帶權(quán)有向邊<Vi,Vj>上,其繼續(xù)時(shí)間用dur(<Vi,Vj>)表示,那么有e[k]=ve[i]；l[k]=vl[j]-dur(<Vi,Vj>)；k=1,2,…,e。這樣就得到計(jì)算關(guān)鍵途徑的算法。為了簡(jiǎn)化算法,假定在求關(guān)鍵途徑之前曾經(jīng)對(duì)各頂點(diǎn)實(shí)現(xiàn)了拓?fù)渑判?并按拓?fù)溆行虻捻樞驅(qū)Ω黜旤c(diǎn)重新進(jìn)展了編號(hào)。最后得到的拓?fù)溆行蛐蛄袨镃4,C0,C3,C2,C1,C5。除了很小的工程外，普通都可以將工程分為假設(shè)干個(gè)稱作“活動(dòng)〞的子工程，完成了這些活動(dòng)，整個(gè)工程就可以完成了。求ve[i]和vl[i]的遞推公式設(shè)活動(dòng)ak(k=1,2,…,e)在帶權(quán)有向邊<Vi,Vj>上,其繼續(xù)時(shí)間用dur(<Vi,Vj>)表示,那么有C1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C6是從源點(diǎn)V0到頂點(diǎn)Vi的最長(zhǎng)途徑長(zhǎng)度例如,以下圖就是一個(gè)AOE網(wǎng)。從ve[0]=0開場(chǎng)，向前遞推①設(shè)初值ve(i)=0(0≤i≤n-1)⑤時(shí)間余量l[k]-e[k]假設(shè)輸出頂點(diǎn)個(gè)數(shù)少于AOV網(wǎng)絡(luò)的頂點(diǎn)個(gè)數(shù),那么報(bào)告網(wǎng)絡(luò)中存在有向環(huán)。不是任一關(guān)鍵活動(dòng)加速一定能使整個(gè)工程提早。因此,完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)途徑長(zhǎng)度,即在這條途徑上一切活動(dòng)的繼續(xù)時(shí)間之和。對(duì)算法7.12作如下修正得算法7.13：〔算法7.13求各事件的ve〕①設(shè)初值ve(i)=0(0≤i≤n-1)②計(jì)算Vj的直接后繼Vk的ve(k)：假設(shè)ve(j)+dut(<j,k>)>ve(k)那么ve(k)=ve(j)+dut(<j,k>)③為求vl，設(shè)一棧記錄拓?fù)溆行蛐蛄?，之后彈棧求逆拓?fù)溆行蛐蛄兴惴?.14〔先求各事件的vl，再求各活動(dòng)的e和l〔7.14中用ee和el表示〕，當(dāng)某個(gè)活動(dòng)的e=l，那么該活動(dòng)是關(guān)鍵活動(dòng)〕1324a1=8a2=125678a10=12a9=6a8=18a5=28a6=8a7=6a3=14a4=10VeVl123456780812222840465808122228404658el0081212222228404600