拓?fù)渑判蛟趺醋龅?？　　對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進行拓?fù)渑判?，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u，v)∈E(G)，

拓?fù)渑判蛟趺醋龅模?/h2>

　　對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進行拓?fù)渑判?，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u，v)∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓?fù)浯涡?Topological Order)的序列，簡稱拓?fù)湫蛄?。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓?fù)渑判颉?

拓?fù)渑判蚴窃趺催M行的？

由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械耐負(fù)渑判蛩惴ㄖ饕茄h(huán)執(zhí)行以下兩步，直到不存在入度為0的頂點為止。(1) 選擇一個入度為0的頂點并輸出之；(2) 從網(wǎng)中刪除此頂點及所有出邊。循環(huán)結(jié)束后，若輸出的頂點數(shù)小于網(wǎng)中的頂點數(shù)，則輸出“有回路”信息，否則輸出的頂點序列就是一種拓?fù)湫蛄小?

拓?fù)渑判蚝完P(guān)鍵路徑是如何實現(xiàn)的？

拓?fù)渑判虻膶崿F(xiàn)步驟：由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械耐負(fù)渑判蛩惴ㄖ饕茄h(huán)執(zhí)行以下三步，直到不存在入度為0的頂點為止；(1)選擇一個入度為0的頂點并輸出之；(2)從網(wǎng)中刪除此頂點及所有出邊；(3)循環(huán)結(jié)束后，若輸出的頂點數(shù)小于網(wǎng)中的頂點數(shù)，則輸出“有回路”信息，否則輸出的頂點序列就是一種拓?fù)湫蛄?。求關(guān)鍵路徑的算法：(1)輸入e條弧<j，k>，建立AOE網(wǎng)的存儲結(jié)構(gòu)。(2)從源點v1出發(fā)，令ve(1)=0，求ve(j)2<=j<=n。(3)從匯點vn出發(fā)，令vl(n)=ve(n)，求vl(i)1<=i<=n-1。(4)根據(jù)各頂點的ve和vl值，求每條弧s（活動）的最早開始時間e(s)和最晚開始時間l(s)，其中e(s)=l(s)的為關(guān)鍵活動。