【正文】 o s t域012345k = 1將 b 加 入 U 集 中將 c 加 入 U 集 后 ， 更 新c l o s e d g e 數(shù) 組a 0c 5a 0f 0b 3c 0a d j v e x 域 l o w c o s t域012345找 到 并 輸 出 代 價(jià) 最 小的 邊 ( b , e ) ， 此 時(shí) k = 4a 0c 0a 0f 0c 0c 0a d j v e x 域 l o w c o s t域012345k = 4k = 4a 0c 0a 0f 0b 0c 0a d j v e x 域 l o w c o s t域012345k = 4將 4 加 入 U 集 中將 c 加 入 U 集 后 ， 更 新c l o s e d g e 數(shù) 組( 1 ) 代 價(jià) 最 小 的 邊 為 ( a , c ) ( 2 ) 代 價(jià) 最 小 的 邊 為 ( c , f )( 3 ) 代 價(jià) 最 小 的 邊 為 ( f , d )( 4 ) 代 價(jià) 最 小 的 邊 為 ( c , b )( 5 ) 代 價(jià) 最 小 的 邊 為 ( b , e ) 圖的連通性問(wèn)題 2．克魯斯卡爾算法 克魯斯卡爾算法從另一途徑求網(wǎng)的最小生成樹(shù)，連通網(wǎng)為N={V,E}，則令最小生成樹(shù)的初始狀態(tài)為只有 n個(gè)頂點(diǎn)而無(wú)邊的非連通圖 T={V,{}}，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在 E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在 T中不同的連通分量中，則將此邊加入到 T中，否則舍去此邊而選擇下一條代價(jià)最小的邊。依次類推，直至 T中所有頂點(diǎn)都在同一連通分量上為止。 例如，圖 N利用卡魯斯卡爾算法構(gòu)造最小生成樹(shù)的過(guò)程如圖 。 b de fc( a ) 初 始 狀 態(tài)ab de fc( b ) 邊 a c 加 入 集 合 E 中a1b de fc2( c ) 邊 d f 加 入 集 合 E 中a1b de fc2( d ) 邊 b c 加 入 集 合 E 中a1b de fc42( e ) 邊 c f 加 入 集 合 E 中a1b de fc3425( f ) 邊 b c 加 入 集 合 E 中a13 有向無(wú)環(huán)圖 AOV網(wǎng)與拓?fù)渑判? 1．什么是 AOV網(wǎng) 幾乎所有的工程都可分為若干個(gè)稱為活動(dòng)的子工程，而這些子工程之間，通常受一些條件的制約，如某些子工程的開(kāi)始必須在另一些子工程完成之后才能進(jìn)行。若用圖的頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)之間的優(yōu)先關(guān)系的有向無(wú)環(huán)圖稱為 AOV網(wǎng)（ activity on vertex work），即頂點(diǎn)表示活動(dòng)的網(wǎng)。 在 AOV網(wǎng)中，若從頂點(diǎn) vi到頂點(diǎn) vj之間存在一條有向路徑，則頂點(diǎn) vi是頂點(diǎn) vj的前驅(qū)，頂點(diǎn) vj為頂點(diǎn) vi的后繼。若 vi,vj是有向網(wǎng)的一條弧，則稱頂點(diǎn) vi是頂點(diǎn) vj的直接前驅(qū)，頂點(diǎn) vj是頂點(diǎn) vi的直接后繼。 有向無(wú)環(huán)圖 例如，一個(gè)軟件工程專業(yè)的學(xué)生必須修完一系列基本課程才能畢業(yè)，其中有些課程是基礎(chǔ)課，它獨(dú)立于其他課程，如 《 高等數(shù)學(xué) 》 ，而另一些課程必須在學(xué)完它的基礎(chǔ)先修課程才能開(kāi)始，如在學(xué)習(xí)完《 程序設(shè)計(jì)基礎(chǔ) 》 和 《 離散數(shù)學(xué) 》 之后才能開(kāi)始學(xué)習(xí) 《 數(shù)據(jù)結(jié)構(gòu) 》 。這些先決條件定義了課程之間的優(yōu)先次序。軟件專業(yè)的課程及先決條件如表 。 表 軟件工程專業(yè)課程關(guān)系表 課 程 編 號(hào)課 程 名 稱先 修 課 程 編 號(hào)C1C2C3C4C5C6C7C8高 等 數(shù) 學(xué)程 序 設(shè) 計(jì) 基 礎(chǔ)離 散 數(shù) 學(xué)數(shù) 據(jù) 結(jié) 構(gòu)算 法 設(shè) 計(jì) 與 分 析普 通 物 理計(jì) 算 機(jī) 組 成 原 理操 作 系 統(tǒng)編 譯 原 理線 性 代 數(shù)C9C1 0無(wú)無(wú)C1C2, C3C4, C7C6C1C1, C2C4, C5C2, C4 有向無(wú)環(huán)圖 這些課程之間的關(guān)系用有向圖可以更清楚的表示 ， 如圖 示 。 圖中的弧表示課程之間的制約關(guān)系 。 C2C3C5C4C9C7C8C6C1 0C1 有向無(wú)環(huán)圖 2．拓?fù)渑判? 拓?fù)渑判虻姆椒ㄈ缦拢? （ 1）在有向圖中任意選擇一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)即頂點(diǎn)入度為零，將該頂點(diǎn)輸出； （ 2）從圖中刪除該頂點(diǎn)和所有以它為尾的??； （ 3）重復(fù)執(zhí)行步驟（ 1）和（ 2），直至所有頂點(diǎn)均已被輸出，或者當(dāng)前 圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止（說(shuō)明有向圖中存在環(huán)）。 按照以上方法，可得到圖 (當(dāng)然還可構(gòu)造其他的拓?fù)湫蛄?)為： (C1,C6,C10,C7,C2,C3,C4,C5,C8,C9)和 (C2,C1,C3,C4,C5,C9,C10,C6,C7,C8) 圖 。其拓?fù)湫蛄袨椋?VV V V V V6。 V1V2V3V5V4V6V2V3V5V4V6V3V5V4V6V6有 向 圖 輸 出 V1后 輸 出 V2后輸 出 V5后V3V5V6輸 出 V4后V5V6輸 出 V3后 有向無(wú)環(huán)圖 AOE網(wǎng)與關(guān)鍵路徑 AOV網(wǎng)描述了活動(dòng)之間的優(yōu)先關(guān)系，是一個(gè)定性的研究，而AOE網(wǎng)就是一個(gè)定量的研究。如整個(gè)工程的最短完成時(shí)間、各個(gè)子工程影響整個(gè)工程的程度、每個(gè)子工程的最短完成時(shí)間和最長(zhǎng)完成時(shí)間，都需要利用 AOE網(wǎng)的相關(guān)知識(shí)來(lái)解決，通過(guò)研究事件與活動(dòng)之間的關(guān)系，從而可以確定整個(gè)工程的最短完成時(shí)間，明確活動(dòng)之間的相互影響，確保整個(gè)工程的順利進(jìn)行。 1．什么是 AOE網(wǎng) AOE網(wǎng)（ activity on edge）即邊表示活動(dòng)的網(wǎng)。 AOE網(wǎng)是一個(gè)帶權(quán)的有向無(wú)環(huán)圖，其中，頂點(diǎn)表示事件（ event），弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)的時(shí)間，權(quán)值表示子工程的活動(dòng)需要的時(shí)間。通常，可用 AOE網(wǎng)估算工程的完成時(shí)間。 有向無(wú)環(huán)圖 圖 11個(gè)活動(dòng)的 AOE網(wǎng) ， 其中 v1， v2， … ， v9表示 9個(gè)事件 ， v1,v2， v1,v3， … ， v8,v9表示 11個(gè)活動(dòng) ，a1， a2， … ， a11表示活動(dòng)的執(zhí)行時(shí)間 。 進(jìn)入頂點(diǎn)的有向弧表示的活動(dòng)已經(jīng)完成 ， 從頂點(diǎn)出發(fā)的有向弧表示的活動(dòng)可以開(kāi)始 。 頂點(diǎn) v1表示整個(gè)工程的開(kāi)始 ， v9表示整個(gè)工程的結(jié)束 。 頂點(diǎn) v5表示活動(dòng) aa5已經(jīng)完成 ， 活動(dòng) a7和 a8可以開(kāi)始 。 完成活動(dòng) a1和活動(dòng) a2分別需要6天和 4天 。 V1V2V3V5V4V7V9V8a1= 6a2= 4a3= 5a4= 1a5= 1a6= 2a7= 9a8= 7a1 0= 2a1 1= 4V6a9= 4 有向無(wú)環(huán)圖 2．關(guān)鍵路徑 AOE網(wǎng)需要研究的問(wèn)題是：（ 1）完成整個(gè)工程至少需要多少時(shí)間？（ 2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？ 由于在 AOE網(wǎng)中有些活動(dòng)可以并行進(jìn)行，所以完成工程的最短時(shí)間是從開(kāi)始點(diǎn)到完成點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度，這里所說(shuō)的路徑長(zhǎng)度是指路徑上各個(gè)活動(dòng)持續(xù)時(shí)間之和。最長(zhǎng)的路徑就是關(guān)鍵路徑（ critical path）。 在 AOE網(wǎng)中，有些活動(dòng)是可以并行執(zhí)行的，關(guān)鍵路徑其實(shí)就是完成工程的最短時(shí)間所經(jīng)過(guò)的路徑。關(guān)鍵路徑表示了完成工程的最短工期。 有向無(wú)環(huán)圖 （ 1）事件 vi的最早發(fā)生時(shí)間 ve(i)：從源點(diǎn)到頂點(diǎn) vi的最長(zhǎng)路徑長(zhǎng)度，稱為事件 vi的最早發(fā)生時(shí)間，記作 ve(i)。求解 ve(i)可以從源點(diǎn) ve(0)=0開(kāi)始，按照拓?fù)渑判蛞?guī)則根據(jù)遞推得到： ve(i)=Max{ve(k)+dut(k,i)|k,i∈ T,1≤i≤n1} 其中， T是所有以第 i個(gè)頂點(diǎn)為弧頭的弧的集合， dut(k,i)表示弧 k,i對(duì)應(yīng)的活動(dòng)的持續(xù)時(shí)間。例如，已知 v2的最早發(fā)生時(shí)間為 ve(2)=6， v3的最早發(fā)生時(shí)間為 ve(3)=4，活動(dòng) a4和 a5的持續(xù)時(shí)間為 1，故 v5的最早發(fā)生時(shí)間為 ve(5)=Max(6+1,4+1)=7。如圖。 V1V2V3V5a1= 6a2= 4a3= 5a4= 1a5= 1v5的 最 早 發(fā) 生 時(shí) 間 為 7v e ( 2 ) = 6v e ( 3 ) = 4v e ( 5 ) = M a x { 6 + 1 ， 4 + 1 ) = 7 2 , 5 持 續(xù) 時(shí) 間 為 1 3 , 5 持 續(xù) 時(shí) 間 為 1 有向無(wú)環(huán)圖 （ 2）事件 vi的最晚發(fā)生時(shí)間 vl(i)：在保證整個(gè)工程正常完成的前提下，活動(dòng)的最遲開(kāi)始時(shí)間，記作 vl(i)。在求解事件 vi的最早發(fā)生時(shí)間 ve(i)的前提 vl(n1)=ve(n1)下，從匯點(diǎn)開(kāi)始，向源點(diǎn)推進(jìn)得到 vl(i)： vl(i)=Min{vl(k)dut(i,k)|i,k∈ S,0≤i≤n2} 其中， S是所有以第 i個(gè)頂點(diǎn)為弧尾的弧的集合， dut(i,k)表示弧 i,k對(duì)應(yīng)的活動(dòng)的持續(xù)時(shí)間。 （ 3）活動(dòng) ai的最早開(kāi)始時(shí)間 e(i)：如果弧 vk,vj表示活動(dòng) ai，當(dāng)事件 vk發(fā)生之后，活動(dòng) ai才開(kāi)始。因此，事件 vk的最早發(fā)生時(shí)間也就是活動(dòng) ai的最早開(kāi)始時(shí)間，即 e(i)=ve(k)。 有向無(wú)環(huán)圖 （ 4） 活動(dòng) ai的最晚開(kāi)始時(shí)間 l(i)：在不推遲整個(gè)工程完成時(shí)間的基礎(chǔ)上 ， 活動(dòng) ai最遲必須開(kāi)始的時(shí)間 。 如果弧 vk,vj表示活動(dòng) ai，持續(xù)時(shí)間為 dut(k,j)， 則活動(dòng) ai的最晚開(kāi)始時(shí)間 l(i)=vl(j)dut(k,j)。 例如 ， 因事件 v8的最晚開(kāi)始時(shí)間為 14， 活動(dòng) a8的持續(xù)時(shí)間為 7， 所以 a8的最晚開(kāi)始時(shí)間為 147=7。 如圖 。 （ 5） 活動(dòng) ai的松弛時(shí)間：活動(dòng) ai的最晚開(kāi)始時(shí)間與最早開(kāi)始時(shí)間之差就是活動(dòng) ai的松弛時(shí)間 ， 記作 l(i)e(i)。 V1V2V3V5V4V8a1= 6a2= 4a3= 5a4= 1a5= 1a6= 2a8= 7V6a9= 4最 晚 開(kāi) 始 時(shí) 間 為 1 4活 動(dòng) a8的 持 續(xù) 時(shí) 間 為 7a8的 最 晚 開(kāi) 始 時(shí) 間 為 1 4 7 = 7 有向無(wú)環(huán)圖 求關(guān)鍵路徑的算法如下： （ 1）對(duì)網(wǎng)中的頂點(diǎn)進(jìn)行拓?fù)渑判?，如果得到的拓?fù)湫蛄许旤c(diǎn)個(gè)數(shù)小于網(wǎng)中頂點(diǎn)數(shù)，則說(shuō)明網(wǎng)中有環(huán)存在，不能求關(guān)鍵路徑，終止算法。否則，從源點(diǎn) v0開(kāi)始，求出各個(gè)頂點(diǎn)的最早發(fā)生時(shí)間 ve(i)。 （ 2）從匯點(diǎn) vn出發(fā) vl(n1)=ve(n1)，按照逆拓?fù)湫蛄星笃渌旤c(diǎn)的最晚發(fā)生時(shí)間 vl(i)。 （ 3）由各頂點(diǎn)的最早發(fā)生時(shí)間 ve(i)和最晚發(fā)生時(shí)間 vl(i)，求出每個(gè)活動(dòng) ai的最早開(kāi)始時(shí)間 e(i)和最晚開(kāi)始時(shí)間 l(i)。 （ 4）找出所有滿足條件 e(i)=l(i)的活動(dòng) ai， ai即是關(guān)鍵活動(dòng)。 有向無(wú)環(huán)圖 利用 AOE網(wǎng)的關(guān)鍵路徑算法 ， 圖 早發(fā)生時(shí)間 ve、 最晚發(fā)生時(shí)間 vl及弧對(duì)應(yīng)活動(dòng)最早發(fā)生時(shí)間 e、 最晚發(fā)生時(shí)間如圖 。 V7a7= 9a1 0= 2 頂 點(diǎn) v e v l 活 動(dòng) e l l ev1v2v3v4v5v6