在圖論中，由某個集合上的偏序得到全序的策略就是拓補排序算法。拓撲排序常出現(xiàn)在涉及偏序關系的問題中，例如時序的先后、事物的依賴等。針對這些問題拓撲排序通常能有效地給出可行解。

為了便于理解，我們先來看一個實例，開源軟件常使用GNU make工具來管理項目的構建，這里的“項目”是由若干個“對象”構成的。Makefile文件則描述了這些“對象”的構建規(guī)則，即給出一系列對象間的依賴關系。若對象A依賴于對象B，則說明對象B必須先于對象A構建，否則構建將無法進行。make的任務就是合理安排各個對象構建的先后順序，使得過程能順利地完成。

作為例子，一個Makefile文件的內容如下：每行描述一個規(guī)則。例如第一行指明對象foo.o和bar.o必須先于target構建。

target: foo.o bar.o

foo.o: foo.c foo.h

bar.o: bar.c bar.h

我們先對問題進行數(shù)學轉化。離散數(shù)學為我們描述對象間的關系提供了有力工具——偏序。令X為所有要研究的對象的集合。集合X上的一個關系R是偏序，當且僅當R滿足自反性、對稱性、傳遞性。

定義如下關系：xRy：x必須先于y被構建，即y依賴x，因為R滿足偏序的性質，xRy也記為x?y。到此我們成功地對問題進行了建模。接下來使用DAG來表示每個對象間的關系，圖的每一個頂點表示一個對象、有向線段表示關系?起點?終點。

(圖一)

如何合理布局各個對象的構建順序，使得構建過程可以順利地進行下去呢？一種直觀的想法是：先選擇不被其它對象依賴的作為第1個對象；再考慮第2個對象，它除了已選的第1個對象外，不應該被其它對象依賴；選擇第n個對象，它除了前面已選的第1~n-1對象外，不能再被其它對象依賴。按照這個規(guī)則依次選出對象，即可保證構建過程順利結束。

可以認為在DAG中，這種直觀想法是正確的。這種策略的結果用下圖描述，但是，這并不是真正的拓撲排序：

(圖二)

問題在于，得到的圖并沒有反映排序結果，充其量不過把圖重新擺了一個形態(tài)，而圖所描述的關系并沒有本質的改變。如何解決這一問題？這就要引入全序。從圖中直觀地看出，只有部分對象之間具有偏序關系，作為反例，bar.h與bar.c之間無偏序關系，因此R不是集合X上的全序關系。試想在圖中，如果為每一對不能比較的對象，強制添加一個關系u?v(或v?u)，使得集合X中每兩個對象都能建立關系，則R就成為了X上的全序關系，如圖三所示。

(圖三)

按照Hass圖的順序排列各個頂點得到圖三，我們發(fā)現(xiàn)從最底部頂點bar.c出發(fā)，總有一條路徑能走完所有頂點并到達最頂部頂點target，另一個重要的觀察是，對于圖中任意一對頂點u和v，若邊∈Edges，則u在線性序列中出現(xiàn)在v之前，因此我們得到的結果拓撲有序。線性排列所有頂點，如下圖所示：

這個結果便是原問題的拓撲排序。因為添加關系u?v的方法不一定唯一，所以拓撲排序不一定唯一。但無論哪種情況，拓撲排序都滿足一個關鍵的性質：沒有一個節(jié)點指向它前面的節(jié)點，形式化地描述：對于圖中的任意兩個結點u和v，若存在一條有向邊，則在拓撲排序中u一定出現(xiàn)在v前面。這條性質描述了拓撲排序的本質，為我們編寫可行的算法提供了依據(jù)。

另外一些需要補充的定理是，有向圖拓撲排序存在的充分必要條件是圖為DAG(有向無環(huán)圖)，這個結論用于判斷問題是否有解，也可用于判斷一個有向圖是否有環(huán)。

算法的求解過程如下：首先統(tǒng)計所有頂點的入度。然后：

a.

尋找所有入度為0的頂點，追加到結果序列末尾并將其從圖中移除，同時將其所有鄰接頂點的入度減一。

b.

重復a，直到所有頂點都從圖中移除。

算法結束時，所得結果序列便是最終答案。

對于任意一個可能帶環(huán)的有向圖，在尋找入度為0的頂點時，如果找不到，說明圖的拓撲排序是不存在的，即問題無解。

上述的“移除”是邏輯層面的概念，具體實現(xiàn)中，我們不需要真正地將頂點從圖中移除，因為某次a.中找到的入度為0的頂點只可能出現(xiàn)在上一次a.中入度被減一的頂點中。當a找到入度為0的頂點時，就會把它的鄰接頂點的入度減一，這時便可以順便統(tǒng)計入度減為0的頂點，下次a直接從這些入度為0的頂點開始，無需再從整個圖中尋找入度為0的頂點。

最后通過一道UVa的題目來說明算法的具體實現(xiàn)：

UVa10305(Ordering Tasks)

題目大意

給出一堆任務，其中一個任務必須在它依賴的所有任務都完成后才能執(zhí)行。已知任務之間的關系，求可能的執(zhí)行順序。

分析

思路與make的例子一致。這里使用vector存儲鄰接表，數(shù)組deg_in維護每個頂點的入度，隊列que維護每趟中入度被減為0的頂點。

參考代碼

#include #include

#define N 100+2

using namespacestd;static vectorcon[N];static intdeg_in[N];int main(void) {

ios::sync_with_stdio(false);intn,m;while((cin >> n >> m) &&n) {for(int i=1;i<=n;++i) {

con[i].clear();

deg_in[i]= 0;

}for(int i=0; i

cin>> a >>j;

con[a].push_back(j);++deg_in[j];

}//

//找出第一個度為0的頂點// queueque;

vectorans;for(int i=1; i<=n; ++i) {if (!deg_in[i]) {

que.push(i);

}

}//

//求排序中其它n-1個頂點// while(!que.empty()) {int u =que.front();

que.pop();

ans.push_back(u);for(size_t i=0; i

que.push(t);

}

}

}for(size_t i=0; i

cout<< ans[i] << (i==ans.size()-1 ? "" : " ");

}

cout<

}return 0;

}

總結

以上是生活随笔為你收集整理的python 拓扑排序_拓扑排序（topsort）算法详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。