dataStructure_圖的應用DAG/AOV/拓撲排序/AOE/關鍵路徑和關鍵活動

文章目錄

• ​​DAG​​
• ​​AOV​​

• ​​拓撲排序​​
• ​​拓撲排序算法​​

• ​​性能分析​​

• ​​逆拓撲排序​​
• ​​AOE​​

• ​​關鍵路徑​​

• ​​AOE時間點相關概念和問題​​

• ​​
• ​​

• ​​弧的相關時間結點​​

• ​​弧的最早開始時間​​
• ​​弧的最晚開始時間​​
• ​​關鍵活動​​

DAG

• 有向無環圖:GAG=directed acyclic graph

• acyclic/ˌeɪ’saɪklɪk/非周期的；非循環的；無環的
• 有向無環圖是不存在順時針環和逆時針環的圖
• 描述含有公共子表達式的有效工具

AOV

• Activity On Vertex (AOV) Network:

• **a directed graph in whichthe vertices represent tasks or activities and **
• the edges represent precedence relations between tasks.
• AOV網中的活動具有傳遞性,

拓撲排序

• 對DAG的頂點進行的一種排序,使得,若存在A到B的路徑,則在排序中,頂點B出現在A之後
• AOV網有一個或者多個拓撲序列序列

拓撲排序算法

• 周遊所有頂點的入度

• 将所有入度為0的頂點(沒有前驅)壓入棧中
• 輸出這個被彈出的頂點,同時計數已經彈出的頂點個數

• 檢查0度頂點棧,如果棧中非空,則彈出棧頂元素i

• 并且掃描出棧的頂點i指向的頂點(即頂點i的鄰接頂點),将它們的入度減去1(撤掉被彈出元素相關的邊)
• 這樣可能得到新的入度為0的頂點,則把這樣的頂點也壓入棧中

• 檢查拓撲排序是否成功(輸出計數是否和圖的頂點數一緻)

• 如果不一緻,說明被排序圖是不是DAG,而是存在環路的

性能分析

• 如果圖采用鄰接表存儲,那麼時間複雜度為O(|V|+|E|)

• |V|是因為要周遊每個頂點(輸出全部頂點)
• |E|是要通路0度點的鄰接邊,最終全圖的所有邊被通路一遍
• 如果是鄰接矩陣,通路所有邊的時間複雜度為

逆拓撲排序

• 定義上形式和拓撲排序和相似,入度為0改為了出度為0
• 對一個AOV網采用如下步驟進行排序,則稱為逆拓撲排序

• 從AOV網中選擇一個沒有後繼的(出度為0)的頂點,并輸出
• 從網中删除被輸出的元素以及以該元素為終點的有向邊
• 重複上述步驟知道AOV網為空

• 在求解AOE的事件發生最遲時間時,會用到逆拓撲排序

AOE

• Activity On Edge(AOE) Network:

• 用邊表示活動的網絡
• 和AOV一樣,都是DAG
• AOE,AOV的頂點和邊的含義不同

• AOE的邊:表示活動,且邊的權值表示完成該活動的開銷

關鍵路徑

• 具有最大路徑長度的路徑稱為​

  ​關鍵路徑​

  ​

• 完成整個工程所需要的最短時間就是關鍵路徑的長度

• 關鍵路徑上的活動稱為關鍵活動

AOE時間點相關概念和問題

• 教材的緊湊的描述語言

• ve=VertexEarliest
• 它是指,從原點v1到頂點vk的最長路徑長度

• 它可以用一個遞推公式來計算

• 其中,

• vl:VertexLatest
• 類似的,也可以用遞推公式來計算
• //可見,計算事件最晚發生vl依賴于事件最早發生時間ve

弧的相關時間結點

• 有了前面兩個概念的鋪墊,我們可以比較容易的導出:活動弧的最早開始時間和最晚開始時間

弧的最早開始時間

• e=Earliest

弧的最晚開始時間

• 注意,有的弧開始時間可以早或晚一些,但是活動完成需要的時間長度是不變的

關鍵活動

• 滿足e(i)=l(i)的弧(活動)就是關鍵活動

• 無法提前開始,也無法推遲開始

• 關鍵路徑上的活動(弧)都是關鍵活動
• 網絡中的關鍵有時不唯一,對于存在多條關鍵路徑的網,隻有加快被所有關鍵路徑都包括了的關鍵活動才能夠達到縮短工期的目的

• 是以,加快關鍵活動的完成隻是縮短工期的必要條件,不是充分條件(不保證能夠縮短工期)