【正文】 ， 對(duì)設(shè)計(jì)的工程流程圖即給定的 AOV網(wǎng) ， 首先要檢查它是否存在環(huán)路 。 檢查的辦法是構(gòu)造它的頂點(diǎn)的拓?fù)溆行蛐蛄?。 若 AOV網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該 AOV網(wǎng)中必定不存在環(huán) 。 AOV網(wǎng)與拓?fù)渑判蚴纠? ?如下圖中的 AOV網(wǎng)可以有如下拓?fù)溆行蛐蛄校? c1→ c2→ c3→ c4→ c5→ c6→ c7→ c8→ c9→ c10→ c11 和 c2→ c3→ c4→ c1→ c5→ c6→ c11→ c9→ c7→ c8→ c10 ?當(dāng)然還可以構(gòu)造出其它一些拓?fù)溆行蛐蛄?。 拓?fù)溆行蛐蛄械奶攸c(diǎn) ?所構(gòu)造出的拓?fù)溆行蛐蛄械奶攸c(diǎn)是： ?在 AOV網(wǎng)中 ， 若頂點(diǎn) i領(lǐng)先于頂點(diǎn) j， 則在拓?fù)溆行蛐蛄兄腥匀活I(lǐng)先； ?對(duì)于網(wǎng)中無領(lǐng)先關(guān)系的頂點(diǎn) i和 j， 在拓?fù)溆行蛐蛄兄薪⒁粋€(gè)領(lǐng)先關(guān)系 ， 或者 i領(lǐng)先于 j， 或者 j領(lǐng)先于 i。 ?拓?fù)渑判?就是由 AOV網(wǎng)中頂點(diǎn)集合上的偏序關(guān)系得到該集合上的一個(gè)全序關(guān)系的操作 。 對(duì)于任何一項(xiàng)工程中各個(gè)子工程 （ 活動(dòng) ） 的安排 ， 必須按照其中某一個(gè)拓?fù)溆行蛐蛄兄械捻樞蜻M(jìn)行安排 。 AOV網(wǎng)進(jìn)行拓?fù)渑判虻姆椒ê筒襟E ?對(duì) AOV網(wǎng)進(jìn)行拓?fù)渑判虻姆椒ê筒襟E如下： ⑴ 從 AOV網(wǎng)中選擇一個(gè)入度為 0的頂點(diǎn)輸出它； ⑵ 從網(wǎng)中刪去該頂點(diǎn)和以它為尾 （ 即從它出發(fā) ）的所有弧； ⑶ 重復(fù) ⑴ 和 ⑵ ， 直到網(wǎng)中不存在入度為 0的頂點(diǎn)時(shí)止 。 ?操作的結(jié)果有兩種可能 ， 一種是網(wǎng)中全部頂點(diǎn)均已經(jīng)輸出 ， 拓?fù)渑判蛲瓿?；一種是有剩余頂點(diǎn)未被輸出 ， 但無入度為 0的頂點(diǎn) ， 說明網(wǎng)中有環(huán)路 。 AOV網(wǎng)進(jìn)行拓?fù)渑判蚺e例 ?以右圖的 AOV網(wǎng)為例 。 ?網(wǎng)中 v1和 v6入度為 0， 則可選其中之一如 v6輸出之；刪除 v6及弧 v6， v5和 v6， v4之后 ， 只有 v1入度為 0， 輸出 v1并刪除 v1和弧v1， v2， v1， v3， v1， v4；此時(shí) v3和v4入度為 0， 選擇其一如 v4輸出 ， 刪除 v4和弧 v4， v5；現(xiàn)在只有 v3入度為 0， 輸出 v3并刪除 v3和弧 v3， v5與 v3， v2；對(duì)最后剩下的兩個(gè)入度為 0的孤立頂點(diǎn) v2和 v5分別輸出 ， 就完成了拓?fù)渑判?。 ?其過程如右下圖所示 ， 得到的拓?fù)溆行蛐蛄袨?v6→v 1→v 4→v 3→v 2→v 5。 拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn) ?拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)：對(duì) AOV網(wǎng)采用鄰接表存儲(chǔ)結(jié)構(gòu) ， 并且在表頭結(jié)點(diǎn)中增加一個(gè)域 indegree來存放頂點(diǎn)的入度 。 選擇并輸出一個(gè)入度為 0的頂點(diǎn)可通過查表頭數(shù)組實(shí)現(xiàn) ， 而刪除頂點(diǎn)和以它為尾的弧的操作用弧頭頂點(diǎn)的入度減 1來實(shí)現(xiàn) 。 ? AOV網(wǎng)的鄰接表的表示如下圖所示： 拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)舉例 ?例如 ， 在右圖的 AOV網(wǎng)中 ， 其中 v6的入度為 0，在輸出 v6后可將 v4和 v5的入度分別由 2和 3減為 1和 2。 為了避免重復(fù)檢測入度為 0的頂點(diǎn) ， 可把所有入度為 0的頂點(diǎn)保存于一鏈棧中 ， 每當(dāng)輸出從棧中彈出一個(gè) ， 每當(dāng)出現(xiàn)新的入度為 0的頂點(diǎn)便壓入之 。 其算法步驟如下： ⑴ 將所有入度為 0的頂點(diǎn)入棧； ⑵ 彈出棧頂元素輸出 ， 并把各鄰接頂點(diǎn)的入度域值減 1； ⑶ 將新產(chǎn)生的入度為 0的頂點(diǎn)入棧； ⑷ 重復(fù) ⑵ 、 ⑶ 兩步 ， 直到?？諘r(shí)為止 。 拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)（續(xù)） ?在這里棧僅起保存入度為 0的頂點(diǎn)的作用 ， 入度為0的頂點(diǎn)誰先誰后無關(guān)緊要 ， 故也可以用鏈隊(duì)列或數(shù)組來保存 。 ?可借用值為 0的入度域 indegree存放鏈中的指針 ，把入度域?yàn)?0的表頭結(jié)點(diǎn)鏈接起來形成鏈棧 。 拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)舉例 ?對(duì)于前面所舉的示例 AOV網(wǎng)的鄰接表 ， 入度域初始狀態(tài)和棧狀態(tài)如右圖 (a)所示； ?執(zhí)行算法步驟 ⑴ 后狀態(tài)如右圖所示 ， 此時(shí)棧頂指針 top指向頂點(diǎn) v6的表頭結(jié)點(diǎn) ， 其 indegree域值為 1（ 即指向頂點(diǎn)v1的表頭結(jié)點(diǎn) ） ， 而 v1的表頭結(jié)點(diǎn)的 indegree域值為 0（ 即為鏈尾結(jié)點(diǎn) ） ； ?執(zhí)行步驟 ⑵ 后輸出 v6， 并將 v5和 v4的表頭結(jié)點(diǎn)的入度域減1， 未產(chǎn)生入度為 0的新頂點(diǎn) ， 步驟 ⑶ 相當(dāng)于空操作；棧頂指針 top=1， 如右圖 (c)所示； ?再次執(zhí)行步驟 ⑵ 輸出 v1， 并將 v4， v3和 v2的表頭結(jié)點(diǎn)的入度域減 1， 產(chǎn)生了兩個(gè)入度為 0的新頂點(diǎn) v4和 v3， 執(zhí)行步驟⑶ 后鏈棧中只有這兩個(gè)結(jié)點(diǎn) ， 棧頂指針 top=3而 v3的入度域?yàn)?4指向 v4， v4的入度域?yàn)?0是鏈尾 ， 如右圖 (d)所示； ?其余的依此類推 ， 分表如右圖的 (e)到 (h)所示 。 鄰接表的表結(jié)點(diǎn)和表頭結(jié)點(diǎn)的定義 ? AOV網(wǎng)的鄰接表的表結(jié)點(diǎn)和表頭結(jié)點(diǎn)的定義可形式化描述如下： typedef struct node /*表結(jié)點(diǎn) */ { int adjvex。 struct node *next。 } nodetype。 /*表結(jié)點(diǎn)類型 */ typedef struct frontnode /*表頭結(jié)點(diǎn) */ { vertextype data。 int indegree。 struct node *next }frontnodetype。 /*鄰接表結(jié)點(diǎn)類型 */ typedef frontnodetype adjlist[maxvernum]。 /*鄰接表類型 */ 拓?fù)渑判蛩惴捎?C語言描述 ?拓?fù)渑判蛩惴捎?C語言描述如下 。 函數(shù) toposort值為 0時(shí)說明 AOV網(wǎng)中存在環(huán)路 ， 無法給出所有頂點(diǎn)的拓?fù)溆行蛐蛄校环駝t為 1時(shí)拓?fù)渑判虺晒?， 輸出 AOV網(wǎng)中全部頂點(diǎn)的拓?fù)溆行蛐蛄?。 int toposort(adjlist g[],int n) {int i,j,k,m=0。 int top=0。 nodetype *p。 for(i=1。i=n。i++) if(g[i].indegree==0) {g[i].indegree=top。 top=i。} 拓?fù)渑判蛩惴捎?C語言描述續(xù) while(top!=0) /*開始拓?fù)渑判?*/ {j=top。 top=g[top].indegree。 printf(“%d\t”,g[j].data)。 m++。 p=g[j].next。 while(p!=NULL) /*當(dāng)?shù)?j個(gè)鏈表不空 */ {k=padjvex。 g[k].indegree。 if(g[k].indegree==0) {g[k].indegree=top。 top=k。 } p=pnext。} } 拓?fù)渑判蛩惴捎?C語言描述續(xù) if(mn) {printf(“The AOV work has a cycle\t”)。 return 0。 } else return 1。 /*否則返回１ */ ｝ ?分析算法的時(shí)間復(fù)雜度為：對(duì) n個(gè)頂點(diǎn) e條邊的 AOV網(wǎng)建立鄰接表需 O(n+e)的時(shí)間；搜索入度為０的頂點(diǎn)需 O(n)的時(shí)間；在拓?fù)渑判蜻^程中若 AOV網(wǎng)無環(huán)路 ， 每個(gè)頂點(diǎn)進(jìn)一次棧出一次棧各 n次 ， 入度減１的操作 g[k].indegree共執(zhí)行 e次 ， 所需時(shí)間為Ｏ (n+e)。 所以算法總的時(shí)間復(fù)雜度為Ｏ(n+e)。 有向無環(huán)圖及其應(yīng)用 有向無環(huán)圖的概念 AOV網(wǎng)與拓?fù)渑判? AOE網(wǎng)與關(guān)鍵路徑 AOE網(wǎng) ?如果在有向圖中用頂點(diǎn)表示事件 ， 用弧表示活動(dòng) ，用弧上的權(quán)表示活動(dòng)持續(xù)時(shí)間 ， 我們稱該帶權(quán)有向圖 （ 即有向網(wǎng) ） 為邊表示活動(dòng)的網(wǎng) （ activity on edge work） ， 簡稱為 AOE網(wǎng) 。 ?在 AOE網(wǎng)中 ， 只有當(dāng)一個(gè)頂點(diǎn)代表的事件發(fā)生后 ，從該頂點(diǎn)出發(fā)的各個(gè)弧所代表的活動(dòng)才能開始；只有以弧頭關(guān)聯(lián)一個(gè)頂點(diǎn)的各個(gè)弧所代表的活動(dòng)都已結(jié)束 ， 該頂點(diǎn)所代表的事件才能發(fā)生 。 AOE網(wǎng)示例 ?如下圖給出的 AOE網(wǎng)中有 9個(gè)事件和 11個(gè)活動(dòng) ， 只有當(dāng)事件 v1發(fā)生后 ， a a2和 a3三個(gè)活動(dòng)才能開始；只有當(dāng) a a5兩個(gè)活動(dòng)結(jié)束 ， 事件 v5才能發(fā)生 。 AOE網(wǎng)與關(guān)鍵路徑 ?一項(xiàng)工程可以由若干子工程 （ 活動(dòng) ） 組成 。 用 AOV網(wǎng)表示這項(xiàng)工程所關(guān)心的是各子工程之間的優(yōu)先次序 ， 即所得到的拓?fù)溆行蛐蛄?；而?AOE網(wǎng)表示這項(xiàng)工程所關(guān)心的是完成整個(gè)工程至少需要多少時(shí)間 ， 哪些子工程是影響整個(gè)工程進(jìn)度的關(guān)鍵活動(dòng) ， 如何加快整個(gè)工程的進(jìn)度等問題 。 ?若前例中圖中給出的 AOE網(wǎng)表示一項(xiàng)工程 ， v1表示整個(gè)工程的開始即源點(diǎn) ， v9表示整個(gè)工程的結(jié)束即匯點(diǎn) ， 和活動(dòng)相關(guān)聯(lián)的數(shù) （ 弧上的權(quán) ） 表示活動(dòng)持續(xù)天數(shù) ， 我們所關(guān)心的是從v1到 v9至少需要多少天 ， 影響工程的關(guān)鍵活動(dòng)是哪些 ， 以及如何加快工程進(jìn)度 。 AOE網(wǎng)與關(guān)鍵路徑（續(xù)） ? 由于在 AOE網(wǎng)中某些活動(dòng)可以并行進(jìn)行 ， 所以完成工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最大路徑長度 （ 指路徑上各活動(dòng)持續(xù)時(shí)間之和最大 ， 而不是路徑上弧的數(shù)目最多 ） 。 ?把從源點(diǎn)到匯點(diǎn)路徑長度最大的路徑稱作 關(guān)鍵路徑 (critical path)， 關(guān)鍵路徑上的活動(dòng)稱作 關(guān)鍵活動(dòng) 。 ?關(guān)鍵路徑的長度是整個(gè)工程所需的最短工期 ， 加快關(guān)鍵活動(dòng)的完成是加快工程進(jìn)度縮短工期的關(guān)鍵 。 ?例如前例圖中 AOE 網(wǎng)表示的 工程 ， 其 關(guān)鍵路徑為v1→v 2→v 5→v 8→v 9， 關(guān)鍵路徑的長度為 18， 工程至少 18天才能完成 ， 關(guān)鍵活動(dòng)為 a a a a11四個(gè)活動(dòng) ， 加快這幾個(gè)活動(dòng)的完成可以縮短工期 。 求關(guān)鍵路徑和確定關(guān)鍵活動(dòng) ?對(duì)于一個(gè) AOE網(wǎng)如何求其關(guān)鍵路徑并確定其關(guān)鍵活動(dòng)呢 ？ 為此 ， 這里引入兩個(gè)概念及遞推公式： ⑴ 事件 vk的最早發(fā)生時(shí)間 ve[k]， 即從源點(diǎn)到 vk的最大路徑長度 ， 它決定了從 vk開始的活動(dòng) （ 即以 vk為弧尾的弧 ） 最早的開始時(shí)間： ⑵ 事件 vk的最遲發(fā)生時(shí)間 ve[k]， 即不推遲工期的前提下允許 vk的最遲發(fā)生時(shí)間 ， 它決定了到 vk結(jié)束的活動(dòng) （ 即以 vk為弧頭的弧 ） 最遲的結(jié)束時(shí)間； ?其中： S[k]表示所有以 vk為弧尾的弧的集合 。 ?注意 ， 要求弧的最遲開始時(shí)間 ， 還得由其最遲結(jié)束時(shí)間 [k]減去弧上的權(quán)值 。 求關(guān)鍵路徑和確定關(guān)鍵活動(dòng) (續(xù) ) ? 前面兩個(gè)遞推公式的計(jì)算 ， 必須分別在拓?fù)溆行蚝湍嫱負(fù)溆行虻那疤嵯逻M(jìn)行 。 ?也就是說 ve[k]必須在 vk的所有前趨頂點(diǎn)的最早發(fā)生時(shí)間求得之后才能確定 ， 而 [k]必須在 vk的所有后繼頂點(diǎn)的最遲發(fā)生時(shí)間求得之后才能確定 。 ?因此 ， 可以在拓?fù)渑判虻幕A(chǔ)上 （ 即按拓?fù)溆行蛐蛄谢蚰嫱負(fù)溆行蛐蛄?） 計(jì)算 ve[k]和 [k]。 求關(guān)鍵路徑和確定關(guān)鍵活動(dòng) (續(xù) ) ?求 AOE網(wǎng)關(guān)鍵路徑算法的步驟： ⑴ 輸入 e條弧 vj， vk， 建立 AOE網(wǎng)的存儲(chǔ)結(jié)構(gòu)； ⑵ 從源點(diǎn) v1出發(fā) ， 令 ve[1]=0， 按拓?fù)溆行蛐蛄写涡蚯笃溆喔黜旤c(diǎn)的最早發(fā)生時(shí)間 ve[k](2≤k≤n)， ve[k]=max{ve[j]+dut(vj， vk)}；如果得到的拓?fù)溆行蛐蛄兄许旤c(diǎn)個(gè)數(shù)小于網(wǎng)中頂點(diǎn)個(gè)數(shù) n， 說明網(wǎng)中存在環(huán)路 ， 不能求關(guān)鍵路徑算法終止 ， 否則執(zhí)行步驟 ⑶ ； ⑶ 從匯點(diǎn) vn出發(fā) ， 令 [n]=ve[n]， 按逆拓?fù)溆行蛐蛄写涡蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時(shí)間 [k](n1≥k≥1)， [k]=min{vl[vj ]dut(vk， vj)}； ⑷ 根據(jù)各頂點(diǎn)的 ve值和值 ， 求每條弧的最早開始時(shí)間 e[s]和最遲開始時(shí)間 [s]； e[s]等于弧 s的弧尾頂點(diǎn) vk的最早發(fā)生時(shí)間 ve[k]， 而 [s]等于弧頭頂點(diǎn) vk的最遲發(fā)生時(shí)間 [k]減去弧 s的權(quán)值；若某條弧 s滿足e[s]＝ [s]則為關(guān)鍵活動(dòng) ， 由所有關(guān)鍵活動(dòng)構(gòu)成網(wǎng)的一條或幾條關(guān)鍵路徑 。 AOE網(wǎng)中事件的發(fā)生時(shí)間和活動(dòng)的開始時(shí)間 ?例如 ， 對(duì)前面示例的 AOE網(wǎng) ， 各頂點(diǎn)的最早發(fā)生時(shí)間 ve[k]和最遲發(fā)生時(shí)間 [k]， 以及每條弧的最早開始時(shí)間 e[s]和最遲開始時(shí)間 [s]， 如下表所示： 求關(guān)鍵路徑和確定關(guān)鍵活動(dòng) (續(xù) )