拓撲排序的原理及其實現
本文將從以下幾個方面介紹拓撲排序：
- 拓撲排序的定義和前置條件
- 和離散數學中偏序 / 全序概念的聯系
- 典型實現算法
- Kahn 算法
- 基于 DFS 的算法
- 解的唯一性問題
- 實際例子
定義和前置條件：
定義：將有向圖中的頂點以線性方式進行排序。即對于任何連接自頂點 u 到頂點 v 的有向邊 uv ，在最后的排序結果中，頂點 u 總是在頂點 v 的前面。
如果這個概念還略顯抽象的話，那么不妨考慮一個非常非常經典的例子——選課。我想任何看過數據結構相關書籍的同學都知道它吧。假設我非常想學習一門機器學習的課程，但是在修這么課程之前，我們必須要學習一些基礎課程，比如計算機科學概論， C 語言程序設計，數據結構，算法等等。那么這個制定選修課程順序的過程，實際上就是一個拓撲排序的過程，每門課程相當于有向圖中的一個頂點，而連接頂點之間的有向邊就是課程學習的先后關系。只不過這個過程不是那么復雜，從而很自然的在我們的大腦中完成了。將這個過程以算法的形式描述出來的結果，就是拓撲排序。
那么是不是所有的有向圖都能夠被拓撲排序呢？顯然不是。繼續考慮上面的例子，如果告訴你在選修計算機科學概論這門課之前需要你先學習機器學習，你是不是會被弄糊涂？在這種情況下，就無法進行拓撲排序，因為它中間存在互相依賴的關系，從而無法確定誰先誰后。在有向圖中，這種情況被描述為存在環路。因此，一個有向圖能被拓撲排序的充要條件就是它是一個有向無環圖 (DAG ： Directed Acyclic Graph) 。
偏序 / 全序關系：
偏序和全序實際上是離散數學中的概念。
這里不打算說太多形式化的定義，形式化的定義教科書上或者上面給的鏈接中就說的很詳細。
還是以上面選課的例子來描述這兩個概念。假設我們在學習完了算法這門課后，可以選修機器學習 或者 計算機圖形學。這個 或者 表示，學習機器學習和計算機圖形學這兩門課之間沒有特定的先后順序。因此， 在我們所有可以選擇的課程中，任意兩門課程之間的關系要么是確定的 ( 即擁有先后關系 ) ，要么是不確定的 ( 即沒有先后關系 ) ，絕對不存在互相矛盾的關系 ( 即環路 ) 。 以上就是偏序的意義，抽象而言，有向圖中兩個頂點之間不存在環路，至于連通與否，是無所謂的。所以，有向無環圖必然是滿足偏序關系的。
理解了偏序的概念，那么全序就好辦了。 所謂全序，就是在偏序的基礎之上，有向無環圖中的任意一對頂點還需要有明確的關系 ( 反映在圖中，就是單向連通的關系，注意不能雙向連通，那就成環了 ) 。 可見，全序就是偏序的一種特殊情況。回到我們的選課例子中，如果機器學習需要在學習了計算機圖形學之后才能學習 ( 可能學的是圖形學領域相關的機器學習算法…… ) ，那么它們之間也就存在了確定的先后順序，原本的偏序關系就變成了全序關系。
實際上，很多地方都存在偏序和全序的概念。
比如對若干互不相等的整數進行排序，最后總是能夠得到唯一的排序結果 ( 從小到大，下同 ) 。這個結論應該不會有人表示疑問吧 :) 但是如果我們以偏序 / 全序的角度來考慮一下這個再自然不過的問題，可能就會有別的體會了。
那么如何用偏序 / 全序來解釋排序結果的唯一性呢？
我們知道不同整數之間的大小關系是確定的，即 1 總是小于 4 的，不會有人說 1 大于或者等于 4 吧。這就是說，這個序列是滿足全序關系的。而對于擁有全序關系的結構 ( 如擁有不同整數的數組 ) ，在其線性化 ( 排序 ) 之后的結果必然是唯一的。對于排序的算法，我們評價指標之一是看該排序算法是否穩定，即值相同的元素的排序結果是否和出現的順序一致。比如，我們說快速排序是不穩定的，這是因為最后的快排結果中相同元素的出現順序和排序前不一致了。如果用偏序的概念可以這樣解釋這一現象： 相同值的元素之間的關系是無法確定的。
因此它們在最終的結果中的出現順序可以是任意的。而對于諸如插入排序這種穩定性排序，它們對于值相同的元素，還有一個潛在的比較方式，即比較它們的出現順序，出現靠前的元素大于出現后出現的元素。因此通過這一潛在的比較，將偏序關系轉換為了全序關系，從而保證了結果的唯一性。
拓展到拓撲排序中，結果具有唯一性的條件也是其所有頂點之間都具有全序關系。如果沒有這一層全序關系，那么拓撲排序的結果也就不是唯一的了。在后面會談到，如果拓撲排序的結果唯一，那么該拓撲排序的結果同時也代表了一條哈密頓路徑。
典型實現算法：
Kahn 算法：
摘一段維基百科上關于 Kahn 算法的偽碼描述：
L← Emptylistthatwillcontainthesortedelements
S ← Setofallnodeswithnoincomingedges
while S is non-emptydo
remove a node n from S
insert n into L
foreach node m withanedge e fromnto m do
removeedge e fromthegraph
ifmhasnootherincomingedgesthen
insert m into S
if graphhasedgesthen
return error (graphhasatleastonecycle)
else
return L (a topologicallysortedorder)
不難看出該算法的實現十分直觀，關鍵在于需要維護一個入度為 0 的頂點的集合：
每次從該集合中取出 ( 沒有特殊的取出規則，隨機取出也行，使用隊列/棧也行，下同 ) 一個頂點，將該頂點放入保存結果的 List 中。
緊接著循環遍歷由該頂點引出的所有邊，從圖中移除這條邊，同時獲取該邊的另外一個頂點，如果該頂點的入度在減去本條邊之后為 0 ，那么也將這個頂點放到入度為 0 的集合中。然后繼續從集合中取出 一個頂點…………
當集合為空之后，檢查圖中是否還存在任何邊，如果存在的話，說明圖中至少存在一條環路。不存在的話則返回結果 List ，此 List 中的順序就是對圖進行拓撲排序的結果。
實現代碼：
public class KahnTopological
{
private List<Integer> result; // 用來存儲結果集
private Queue<Integer> setOfZeroIndegree; // 用來存儲入度為0的頂點
private int[] indegrees; // 記錄每個頂點當前的入度
private int edges;
private Digraphdi;
public KahnTopological(Digraphdi)
{
this.di = di;
this.edges = di.getE();
this.indegrees = new int[di.getV()];
this.result = new ArrayList<Integer>();
this.setOfZeroIndegree = new LinkedList<Integer>();
// 對入度為0的集合進行初始化
Iterable<Integer>[] adjs = di.getAdj();
for(int i = 0; i < adjs.length; i++)
{
// 對每一條邊 v -> w
for(int w : adjs[i])
{
indegrees[w]++;
}
}
for(int i = 0; i < indegrees.length; i++)
{
if(0 == indegrees[i])
{
setOfZeroIndegree.enqueue(i);
}
}
process();
}
private void process()
{
while(!setOfZeroIndegree.isEmpty())
{
int v = setOfZeroIndegree.dequeue();
// 將當前頂點添加到結果集中
result.add(v);
// 遍歷由v引出的所有邊
for(int w : di.adj(v))
{
// 將該邊從圖中移除，通過減少邊的數量來表示
edges--;
if(0 == --indegrees[w]) // 如果入度為0，那么加入入度為0的集合
{
setOfZeroIndegree.enqueue(w);
}
}
}
// 如果此時圖中還存在邊，那么說明圖中含有環路
if(0 != edges)
{
throw new IllegalArgumentException("Has Cycle !");
}
}
public Iterable<Integer> getResult()
{
return result;
}
}
對上圖進行拓撲排序的結果：
2->8->0->3->7->1->5->6->9->4->11->10->12
復雜度分析：
初始化入度為 0 的集合需要遍歷整張圖，檢查每個節點和每條邊，因此復雜度為 O(E+V);
然后對該集合進行操作，又需要遍歷整張圖中的，每條邊，復雜度也為 O(E+V);
因此 Kahn 算法的復雜度即為 O(E+V) 。
基于 DFS 的拓撲排序：
除了使用上面直觀的 Kahn 算法之外，還能夠借助深度優先遍歷來實現拓撲排序。這個時候需要使用到棧結構來記錄拓撲排序的結果。
同樣摘錄一段維基百科上的偽碼：
L ← Emptylistthatwillcontainthesortednodes
S ← Setofallnodeswithnooutgoingedges
for each node n in S do
visit(n)
function visit(node n)
if n hasnot beenvisitedyetthen
mark n as visited
for each node m withanedgefrom m to ndo
visit(m)
add n to L
DFS 的實現更加簡單直觀，使用遞歸實現。利用 DFS 實現拓撲排序，實際上只需要添加一行代碼，即上面偽碼中的最后一行： add n to L 。
需要注意的是，將頂點添加到結果 List 中的時機是在 visit 方法即將退出之時。
這個算法的實現非常簡單，但是要理解的話就相對復雜一點。
關鍵在于為什么在 visit 方法的最后將該頂點添加到一個集合中，就能保證這個集合就是拓撲排序的結果呢？
因為添加頂點到集合中的時機是在 dfs 方法即將退出之時，而 dfs 方法本身是個遞歸方法，只要當前頂點還存在邊指向其它任何頂點，它就會遞歸調用 dfs 方法，而不會退出。因此，退出 dfs 方法，意味著當前頂點沒有指向其它頂點的邊了，即當前頂點是一條路徑上的最后一個頂點。
下面簡單證明一下它的正確性：
考慮任意的邊 v->w ，當調用 dfs(v) 的時候，有如下三種情況：
- dfs(w) 還沒有被調用，即 w 還沒有被 mark ，此時會調用 dfs(w) ，然后當 dfs(w) 返回之后， dfs(v) 才會返回
- dfs(w) 已經被調用并返回了，即 w 已經被 mark
- dfs(w) 已經被調用但是在此時調用 dfs(v) 的時候還未返回
需要注意的是，以上第三種情況在拓撲排序的場景下是不可能發生的，因為如果情況 3 是合法的話，就表示存在一條由 w 到 v 的路徑。而現在我們的前提條件是由 v 到 w 有一條邊，這就導致我們的圖中存在環路，從而該圖就不是一個有向無環圖 (DAG) ，而我們已經知道，非有向無環圖是不能被拓撲排序的。
那么考慮前兩種情況，無論是情況 1 還是情況 2 ， w 都會先于 v 被添加到結果列表中。所以邊 v->w 總是由結果集中后出現的頂點指向先出現的頂點。為了讓結果更自然一些，可以使用棧來作為存儲最終結果的數據結構，從而能夠保證邊 v->w 總是由結果集中先出現的頂點指向后出現的頂點。
實現代碼：
public class DirectedDepthFirstOrder
{
// visited數組，DFS實現需要用到
private boolean[] visited;
// 使用棧來保存最后的結果
private Stack<Integer> reversePost;
/**
* Topological Sorting Constructor
*/
public DirectedDepthFirstOrder(Digraphdi, boolean detectCycle)
{
// 這里的DirectedDepthFirstCycleDetection是一個用于檢測有向圖中是否存在環路的類
DirectedDepthFirstCycleDetectiondetect = new DirectedDepthFirstCycleDetection(
di);
if (detectCycle && detect.hasCycle())
throw new IllegalArgumentException("Has cycle");
this.visited = new boolean[di.getV()];
this.reversePost = new Stack<Integer>();
for (int i = 0; i < di.getV(); i++)
{
if (!visited[i])
{
dfs(di, i);
}
}
}
private void dfs(Digraphdi, int v)
{
visited[v] = true;
for (int w : di.adj(v))
{
if (!visited[w])
{
dfs(di, w);
}
}
// 在即將退出dfs方法的時候，將當前頂點添加到結果集中
reversePost.push(v);
}
public Iterable<Integer> getReversePost()
{
return reversePost;
}
}
復雜度分析：
復雜度同 DFS 一致，即 O(E+V) 。具體而言，首先需要保證圖是有向無環圖，判斷圖是 DAG 可以使用基于 DFS 的算法，復雜度為 O(E+V) ，而后面的拓撲排序也是依賴于 DFS ，復雜度為 O(E+V)
還是對上文中的那張有向圖進行拓撲排序，只不過這次使用的是基于 DFS 的算法，結果是：
8->7->2->3->0->6->9->10->11->12->1->5->4
兩種實現算法的總結：
這兩種算法分別使用鏈表和棧來表示結果集。
對于基于 DFS 的算法，加入結果集的條件是：頂點的出度為 0 。這個條件和 Kahn 算法中入度為 0 的頂點集合似乎有著異曲同工之妙，這兩種算法的思想猶如一枚硬幣的兩面，看似矛盾，實則不然。一個是從入度的角度來構造結果集，另一個則是從出度的角度來構造。
實現上的一些不同之處：
Kahn 算法不需要檢測圖為 DAG ，如果圖為 DAG ，那么在出度為 0 的集合為空之后，圖中還存在沒有被移除的邊，這就說明了圖中存在環路。而基于 DFS 的算法需要首先確定圖為 DAG ，當然也能夠做出適當調整，讓環路的檢測和拓撲排序同時進行，畢竟環路檢測也能夠在 DFS 的基礎上進行。
二者的復雜度均為 O(V+E) 。
環路檢測和拓撲排序同時進行的實現：
public class DirectedDepthFirstTopoWithCircleDetection
{
private boolean[] visited;
// 用于記錄dfs方法的調用棧，用于環路檢測
private boolean[] onStack;
// 用于當環路存在時構造之
private int[] edgeTo;
private Stack<Integer> reversePost;
private Stack<Integer> cycle;
/**
* Topological Sorting Constructor
*/
public DirectedDepthFirstTopoWithCircleDetection(Digraphdi)
{
this.visited = new boolean[di.getV()];
this.onStack = new boolean[di.getV()];
this.edgeTo = new int[di.getV()];
this.reversePost = new Stack<Integer>();
for (int i = 0; i < di.getV(); i++)
{
if (!visited[i])
{
dfs(di, i);
}
}
}
private void dfs(Digraphdi, int v)
{
visited[v] = true;
// 在調用dfs方法時，將當前頂點記錄到調用棧中
onStack[v] = true;
for (int w : di.adj(v))
{
if(hasCycle())
{
return;
}
if (!visited[w])
{
edgeTo[w] = v;
dfs(di, w);
}
else if(onStack[w])
{
// 當w已經被訪問，同時w也存在于調用棧中時，即存在環路
cycle = new Stack<Integer>();
cycle.push(w);
for(int start = v; start != w; start = edgeTo[start])
{
cycle.push(v);
}
cycle.push(w);
}
}
// 在即將退出dfs方法時，將頂點添加到拓撲排序結果集中，同時從調用棧中退出
reversePost.push(v);
onStack[v] = false;
}
private boolean hasCycle()
{
return (null != cycle);
}
public Iterable<Integer> getReversePost()
{
if(!hasCycle())
{
return reversePost;
}
else
{
throw new IllegalArgumentException("Has Cycle: " + getCycle());
}
}
public Iterable<Integer> getCycle()
{
return cycle;
}
}
拓撲排序解的唯一性：
哈密頓路徑：
哈密頓路徑是指一條能夠對圖中所有頂點正好訪問一次的路徑。本文中只會解釋一些哈密頓路徑和拓撲排序的關系，至于哈密頓路徑的具體定義以及應用，可以參見本文開篇給出的鏈接。
前面說過，當一個 DAG 中的任何兩個頂點之間都存在可以確定的先后關系時，對該 DAG 進行拓撲排序的解是唯一的。這是因為它們形成了全序的關系，而對存在全序關系的結構進行線性化之后的結果必然是唯一的 ( 比如對一批整數使用穩定的排序算法進行排序的結果必然就是唯一的 ) 。
需要注意的是，非 DAG 也是能夠含有哈密頓路徑的，為了利用拓撲排序來實現判斷，所以這里討論的主要是判斷 DAG 中是否含有哈密頓路徑的算法，因此下文中的圖指代的都是 DAG 。
那么知道了哈密頓路徑和拓撲排序的關系，我們如何快速檢測一張圖是否存在哈密頓路徑呢？
根據前面的討論，是否存在哈密頓路徑的關鍵，就是確定圖中的頂點是否存在全序的關系，而全序的關鍵，就是任意一對頂點之間都是能夠確定先后關系的。因此，我們能夠設計一個算法，用來遍歷頂點集中的每一對頂點，然后檢查它們之間是否存在先后關系，如果所有的頂點對有先后關系，那么該圖的頂點集就存在全序關系，即圖中存在哈密頓路徑。
但是很顯然，這樣的算法十分低效。對于大規模的頂點集，是無法應用這種解決方案的。通常一個低效的解決辦法，十有八九是因為沒有抓住現有問題的一些特征而導致的。因此我們回過頭來再看看這個問題，有什么特征使我們沒有利用的。還是舉對整數進行排序的例子：
比如現在有 3 ， 2 ， 1 三個整數，我們要對它們進行排序，按照之前的思想，我們分別對 (1,2) ， (2,3) ， (1,3) 進行比較，這樣需要三次比較，但是我們很清楚， 1 和 3 的那次比較實際上是多余的。我們為什么知道這次比較是多余的呢？我認為，是我們下意識的利用了整數比較滿足傳遞性的這一規則。但是計算機是無法下意識的使用傳遞性的，因此只能通過其它的方式來告訴計算機，有一些比較是不必要的。所以，也就有了相對插入排序，選擇排序更加高效的排序算法，比如歸并排序，快速排序等，將 n 2 的算法加速到了 nlogn 。或者是利用了問題的特點，采取了更加獨特的解決方案，比如基數排序等。
扯遠了一點，回到正題。現在我們沒有利用到的就是全序關系中傳遞性這一規則。如何利用它呢，最簡單的想法往往就是最實用的，我們還是選擇排序，排序后對每對相鄰元素進行檢測不就間接利用了傳遞性這一規則嘛？所以，我們先使用拓撲排序對圖中的頂點進行排序。排序后，對每對相鄰頂點進行檢測，看看是否存在先后關系，如果每對相鄰頂點都存在著一致的先后關系 ( 在有向圖中，這種先后關系以有向邊的形式體現，即查看相鄰頂點對之間是否存在有向邊 ) 。那么就可以確定該圖中存在哈密頓路徑了，反之則不存在。
實現代碼：
/**
* Hamilton Path Detection for DAG
*/
public class DAGHamiltonPath
{
private boolean hamiltonPathPresent;
private Digraphdi;
private KahnTopologicalkts;
// 這里使用Kahn算法進行拓撲排序
public DAGHamiltonPath(Digraphdi, KahnTopologicalkts)
{
this.di = di;
this.kts = kts;
process();
}
private void process()
{
Integer[] topoResult = kts.getResultAsArray();
// 依次檢查每一對相鄰頂點，如果二者之間沒有路徑，則不存在哈密頓路徑
for(int i = 0; i < topoResult.length - 1; i++)
{
if(!hasPath(topoResult[i], topoResult[i + 1]))
{
hamiltonPathPresent = false;
return;
}
}
hamiltonPathPresent = true;
}
private boolean hasPath(int start, int end)
{
for(int w : di.adj(start))
{
if(w == end)
{
return true;
}
}
return false;
}
public boolean hasHamiltonPath()
{
return hamiltonPathPresent;
}
}
來自：http://blog.jobbole.com/108351/