拓撲序列

拓撲序列是頂點活動網中將活動按發生的先後次序進行的一種排列。 拓撲排序，是對一個有向無環圖(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之前，則我們稱這樣的頂點序列為一個拓撲序列。

相關簡介

有向無環圖（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 的前面。

過程

對於一個給定的有向圖，得到其拓撲序列的步驟如下：
①從圖中選擇一個人度為0的頂點，並輸出該頂點；
②從圖中刪除該頂點及其相關聯的有向邊，調整被刪除有向邊的終點的入度（人度減1）；
③重複①和②；
④直到所有頂點均被輸出，拓撲序列完成；否則，無拓撲序列。
可以證明，任何一個無環的有向圖一定有拓撲序列，有環的有向圖則無拓撲序列。

解釋

該排列滿足：如果圖中有一條從u到v的路徑，則頂點v必須出現在頂點u之後。找出頂點活動網中的拓撲序列稱“拓撲排序”。

套用

拓撲排序既可用深度優先搜尋，也可用廣度優先搜尋實現。