-
拓撲序列
鎖定
拓撲序列是頂點活動網中將活動按發生的先後次序進行的一種排列。 拓撲排序,是對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序,是將G中所有頂點排成一個線性序列,使得圖中任意一對頂點u和v,若邊(u,v)∈E(G),則u在線性序列中出現在v之前。通常,這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列,簡稱拓撲序列。簡單的説,由某個集合上的一個偏序得到該集合上的一個全序,這個操作稱之為拓撲排序。
- 中文名
- 拓撲序列
- 性 質
- 通信信息類科學術語
拓撲序列簡介
在AOV網中,若不存在迴路,則所有活動可排列成一個線性序列,使得每個活動的所有前驅活動都排在該活動的前面,我們把此序列叫做拓撲序列(Topological order)。
設G=(V,E)是一個具有n個頂點的有向圖,V中的頂點序列v1,v2,…,vn,滿足若從頂點vi到vj有一條路徑,則在頂點序列中頂點vi必在vj之前,則我們稱這樣的頂點序列為一個拓撲序列。
[1]
拓撲序列相關簡介
有向無環圖(Directed Acyclic Graph, DAG)是有向圖的一種,字面意思的理解就是圖中沒有環。常常被用來表示事件之間的驅動依賴關係,管理任務之間的調度。
AOV網:在每一個工程中,可以將工程分為若干個子工程,這些子工程稱為活動。如果用概述圖中的頂點表示活動,以有向圖的弧表示活動之間的優先關係,這樣的有向圖稱為AOV網,即頂點表示活動的網。在AOV網中,如果從頂點vi到頂點j之間存在一條路徑,則頂點vi是頂點vj的前驅,頂點vj是頂點vi的後繼。活動中的制約關係可以通過AOV網中的表示。 在AOV網中,不允許出現環,如果出現環就表示某個活動是自己的先決條件。因此需要對AOV網判斷是否存在環,可以利用有向圖的拓撲排序進行判斷。
拓撲排序:拓撲排序是對一個有向圖構造拓撲序列的過程。拓撲排序(Topological Sorting)是一個有向無環圖(DAG, Directed Acyclic Graph)的所有頂點的線性序列。且該序列必須滿足下面兩個條件:
(1)每個頂點出現且只出現一次。
(2)若存在一條從頂點 A 到頂點 B 的路徑,那麼在序列中頂點 A 出現在頂點 B 的前面。
拓撲序列過程
對於一個給定的有向圖,得到其拓撲序列的步驟如下:
②從圖中刪除該頂點及其相關聯的有向邊,調整被刪除有向邊的終點的入度(入度減1);
③重複①和②;
④直到所有頂點均被輸出,拓撲序列完成;否則,無拓撲序列。
拓撲序列解釋
該排列滿足:如果圖中有一條從u到v的路徑,則頂點v必須出現在頂點u之後。找出頂點活動網中的拓撲序列稱“拓撲排序”。
拓撲序列應用
拓撲排序既可用深度優先搜索,也可用廣度優先搜索實現。