[科普中國]-拓撲序列

拓撲序列是頂點活動網(wǎng)中將活動按發(fā)生的先后次序進行的一種排列。 拓撲排序，是對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。

簡介在AOV網(wǎng)中，若不存在回路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅(qū)活動都排在該活動的前面，我們把此序列叫做拓撲序列(Topological order)。

設(shè)G=(V,E)是一個具有n個頂點的有向圖，V中的頂點序列v1,v2,…,vn,滿足若從頂點vi到vj有一條路徑，則在頂點序列中頂點vi必在vj之前，則我們稱這樣的頂點序列為一個拓撲序列。1

相關(guān)簡介**有向無環(huán)圖****（Directed Acyclic Graph, DAG）是有向圖的一種，字面意思的理解就是圖中沒有環(huán)。常常被用來表示事件之間的驅(qū)動依賴關(guān)系，管理任務(wù)之間的調(diào)度。
AOV網(wǎng)：**在每一個工程中，可以將工程分為若干個子工程，這些子工程稱為活動。如果用圖中的頂點表示活動，以有向圖的弧表示活動之間的優(yōu)先關(guān)系，這樣的有向圖稱為AOV網(wǎng)，即頂點表示活動的網(wǎng)。在AOV網(wǎng)中，如果從頂點vi到頂點j之間存在一條路徑，則頂點vi是頂點vj的前驅(qū)，頂點vj是頂點vi的后繼?；顒又械闹萍s關(guān)系可以通過AOV網(wǎng)中的表示。 在AOV網(wǎng)中，不允許出現(xiàn)環(huán)，如果出現(xiàn)環(huán)就表示某個活動是自己的先決條件。因此需要對AOV網(wǎng)判斷是否存在環(huán)，可以利用有向圖的拓撲排序進行判斷。

拓撲排序**：**拓撲排序是對一個有向圖構(gòu)造拓撲序列的過程。拓撲排序（Topological Sorting）是一個有向無環(huán)圖（DAG, Directed Acyclic Graph）的所有頂點的線性序列。且該序列必須滿足下面兩個條件：
（1）每個頂點出現(xiàn)且只出現(xiàn)一次。
（2）若存在一條從頂點 A 到頂點 B 的路徑，那么在序列中頂點 A 出現(xiàn)在頂點 B 的前面。

過程對于一個給定的有向圖，得到其拓撲序列的步驟如下：
①從圖中選擇一個人度為0的頂點，并輸出該頂點；
②從圖中刪除該頂點及其相關(guān)聯(lián)的有向邊，調(diào)整被刪除有向邊的終點的入度（人度減1）；
③重復①和②；
④直到所有頂點均被輸出，拓撲序列完成；否則，無拓撲序列。
可以證明，任何一個無環(huán)的有向圖一定有拓撲序列，有環(huán)的有向圖則無拓撲序列。2

解釋該排列滿足：如果圖中有一條從u到v的路徑，則頂點v必須出現(xiàn)在頂點u之后。找出頂點活動網(wǎng)中的拓撲序列稱“拓撲排序”。

應用拓撲排序既可用深度優(yōu)先搜索，也可用廣度優(yōu)先搜索實現(xiàn)。

本詞條內(nèi)容貢獻者為:

徐恒山 - 講師 - 西北農(nóng)林科技大學