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