拓撲排序怎么做的？　　對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u，v)∈E(G)，

拓撲排序怎么做的？

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

拓撲排序是怎么進行的？

由AOV網(wǎng)構造拓撲序列的拓撲排序算法主要是循環(huán)執(zhí)行以下兩步，直到不存在入度為0的頂點為止。(1) 選擇一個入度為0的頂點并輸出之；(2) 從網(wǎng)中刪除此頂點及所有出邊。循環(huán)結束后，若輸出的頂點數(shù)小于網(wǎng)中的頂點數(shù)，則輸出“有回路”信息，否則輸出的頂點序列就是一種拓撲序列。

拓撲排序和關鍵路徑是如何實現(xiàn)的？

拓撲排序的實現(xiàn)步驟：由AOV網(wǎng)構造拓撲序列的拓撲排序算法主要是循環(huán)執(zhí)行以下三步，直到不存在入度為0的頂點為止；(1)選擇一個入度為0的頂點并輸出之；(2)從網(wǎng)中刪除此頂點及所有出邊；(3)循環(huán)結束后，若輸出的頂點數(shù)小于網(wǎng)中的頂點數(shù)，則輸出“有回路”信息，否則輸出的頂點序列就是一種拓撲序列。求關鍵路徑的算法：(1)輸入e條弧<j，k>，建立AOE網(wǎng)的存儲結構。(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)的為關鍵活動。