[Data Structure & Algorithm] 有向無環圖的拓撲排序及關鍵路徑

基本名稱

• 有向無環圖 - DAG (Directed Acycline Graph)
  • 如果圖的鄰接矩陣中，對角線以上（或以下）均為零，則說明該有向圖為無環圖；反之，不一定成立
• 頂點表示的活動網 - AOV網 (Activity On Vertex Network)
  • 弧上沒有權值
  • 通常用于表示流程圖
• 弧表示的活動網 - AOE網 (Activity On Edge)
  • 弧上的權值 - 活動持續的時間
  • 通常用于估算工程完成的時間
  • 正常情況下（無環），圖中隻有一個入度為0的點（源點）和一個出度為0的點（彙點）
• 弧尾 - 在結點A指向結點B的弧中，結點A為弧尾
• 圖中的結點數量 - n; 圖中的弧數量 - e

拓撲排序 - 基于AOV網

• 分類
  • 全序 - 拓撲有序
    • 集合中所有結點都可比較（經過零個或多個結點後可連接配接）
  • 偏序 - 隻有部分結點是可比較的
• 可以求拓撲排序的圖中不存在環

• 基本思想

  1.周遊圖中沒有前驅（入度為0）的結點

  2.選擇并輸出一個沒有前驅的結點，循環與之相連的結點

  3.删除該結點，和以該頂點作為弧尾的弧

  4.如果下一結點為空，則重複2，3，直到所有結點均已全部輸出（如果圖中還存在有前驅的結點，則說明圖中存在環）

• 具體實作
  • 結點結構 - 資料域（結點的值）|鍊域（指向下一個結點）|資料域（結點的入度）
  • 引入棧
    • 初始化 - 周遊所有結點，儲存所有入度為0的結點
    • 如果在輸出結點并删除弧之後，有新增的入度為0的結點，再壓入棧中
  • 時間複雜度O(n+e)

關鍵路徑 - 基于AOE網

• 定義
  • ve(i) - 事件i的最早開始時間
  • vl(i) - 事件i的最晚開始時間
  • 關鍵路徑 - 長度最長的路徑
  • 關鍵活動 - 關鍵路徑上的所有活動，ve(i) = vl(i)
• 求解關鍵路徑需要在拓撲有序和逆拓撲排序的前提下進行，即圖中也不能存在環

• 基本思路

  1.從源點vi出發，令ve(i) = 0，按拓撲有序求ve(j)，取路徑中的最大值

  2.從彙點vn出發，在彙點上ve(n) = vl(n)，按逆拓撲有序求vl(j)，取路徑中的最小值

  3.所有ve(i)=vl(i)的點都是關鍵活動，其相連即為關鍵路徑

• 具體實作
  • 逆拓撲有序 - 将拓撲排序的序列存儲在棧中，再将棧中元素彈出，即可得到逆拓撲排序
• 什麼情況下，提高關鍵活動，才能對工程的進度産生影響
  • 提高關鍵活動可能導緻關鍵路徑的改變，是以必須在關鍵路徑不變的前提下
  • 關鍵活動必須在所有關鍵路徑上

轉載于:https://www.cnblogs.com/break-dawnn/p/9780764.html