20拓撲排序和關鍵路徑-文庫吧
2025-07-10 15:49 本頁面
【正文】 偏序 全序 拓撲排序 按照有向圖給出的次序關系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關系的頂點，則可以人為加上任意的次序關系。 由此所得頂點的線性序列稱之為拓撲有序序列 拓撲排序 用頂點表示活動，弧表示活動間的優(yōu)先關系的有向圖。 AOV網（ Activity On Vertex NetWork） AOV網中不應該出現(xiàn)有向環(huán)：如果存在環(huán)，則某項活動以自己為先決條件， 拓撲排序 B D A C 可求得拓撲有序序列 ： A B C D 或 A C B D B D A C 不能求得它的拓撲有序序列。 因為圖中存在一個回路 {B, C, D} 拓撲排序 拓撲排序 方法 1 從有向圖中選取一個沒有前驅的頂點，并輸出之 。 從有向圖中刪去此頂點以及所有以它為尾的弧 。 重復上述兩步，直至圖空，或者圖不空但找不到無前驅的頂點為止。 拓撲排序 方法 1 a c g b d h f e b h a c d g f e 拓撲序列 ： 在算法中需要用定量的描述替代定性的概念 沒有前驅的頂點 入度為零的頂點 刪除頂點及以它為尾的弧 弧頭頂點的入度減 1 拓撲排序 方法 1 Status ToplogicalSort(ALGragh G){ FindInDegree(G, indegree)。 InitStack(S)。 for(i=0。i。i++){if(!indegree[i]) push(S,i)。} count=0。 //對輸出頂點計數(shù) while (!EmptyStack(S)) { ………… }//while if (count) return ERROR。 else return OK。 } 拓撲排序 算法 Status ToplogicalSort(ALGragh G){ ……………… while (!EmptyStack(S)) { Pop(S, v)。 ++count。 printf(v)。 for (w=FirstAdj(v)。 w。 w=NextAdj(G,v,w)){ indegree(w)。 // 弧頭頂點的入度減 1 if (!indegree[w]) Push(S, w)。 }//for }//while ……………… } 拓撲排序 算法 總的時間復雜度： O(n+e) 算法分析： 拓撲排序 算法 拓撲排序 方法 2 a c g b d h f e b h a c d g f e 拓撲序列 ： 對有向無環(huán)圖利用 深度優(yōu)先搜索 進行拓撲排序。 拓撲排序 方法 2 a c g b d h f e b h a c d g f e 此圖的一個拓撲序列為： 退出 DFS函數(shù)順序： e f g d c a h b 拓撲排序 方法 2 最先退出 DFS函數(shù)的頂點是出度為零的頂點，為拓撲排序序列中最后一個頂點。 因此，按退出 DFS函數(shù)的先后記錄下來的頂點序列即為逆向的拓撲排序序列。 結論： 拓撲排序 方法 2 void DFSToplogicalSort (Graph G, in
環(huán)評公示相關推薦
鄂ICP備17016276號-1