(文章引用于http://songlee24.github.io/2015/05/07/topological-sorting/）
一、什么是拓撲排序
在圖論中，拓撲排序（Topological Sorting）是一個有向無環(huán)圖（DAG, Directed Acyclic Graph）的所有頂點的線性序列。且該序列必須滿足下面兩個條件：
- 每個頂點出現(xiàn)且只出現(xiàn)一次。
- 若存在一條從頂點 A 到頂點 B 的路徑，那么在序列中頂點 A 出現(xiàn)在頂點 B 的前面。
有向無環(huán)圖（DAG）才有拓撲排序，非DAG圖沒有拓撲排序一說。
例如，下面這個圖：
它是一個 DAG 圖，那么如何寫出它的拓撲排序呢？這里說一種比較常用的方法：
- 從 DAG 圖中選擇一個 沒有前驅（即入度為0）的頂點并輸出。
- 從圖中刪除該頂點和所有以它為起點的有向邊。
- 重復 1 和 2 直到當前的 DAG 圖為空或當前圖中不存在無前驅的頂點為止。后一種情況說明有向圖中必然存在環(huán)。
于是，得到拓撲排序后的結果是 { 1, 2, 4, 3, 5 }。
通常，一個有向無環(huán)圖可以有一個或多個拓撲排序序列。
二、拓撲排序的應用
拓撲排序通常用來“排序”具有依賴關系的任務。
比如，如果用一個DAG圖來表示一個工程，其中每個頂點表示工程中的一個任務，用有向邊 表示在做任務 B 之前必須先完成任務 A。故在這個工程中，任意兩個任務要么具有確定的先后關系，要么是沒有關系，絕對不存在互相矛盾的關系（即環(huán)路）。
三、拓撲排序的實現(xiàn)
根據上面講的方法，我們關鍵是要維護一個入度為0的頂點的集合。
圖的存儲方式有兩種：鄰接矩陣和鄰接表。這里我們采用鄰接表來存儲圖，C++代碼如下：
#include<iostream>
#include <list>
#include <queue>
using namespace std;
/************************類聲明************************/
class Graph
{
int V; // 頂點個數(shù)
list<int> *adj; // 鄰接表
queue<int> q; // 維護一個入度為0的頂點的集合
int* indegree; // 記錄每個頂點的入度
public:
Graph(int V); // 構造函數(shù)
~Graph(); // 析構函數(shù)
void addEdge(int v, int w); // 添加邊
bool topological_sort(); // 拓撲排序
};
/************************類定義************************/
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
indegree = new int[V]; // 入度全部初始化為0
for(int i=0; i<V; ++i)
indegree[i] = 0;
}
Graph::~Graph()
{
delete [] adj;
delete [] indegree;
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
++indegree[w];
}
bool Graph::topological_sort()
{
for(int i=0; i<V; ++i)
if(indegree[i] == 0)
q.push(i); // 將所有入度為0的頂點入隊
int count = 0; // 計數(shù)，記錄當前已經輸出的頂點數(shù)
while(!q.empty())
{
int v = q.front(); // 從隊列中取出一個頂點
q.pop();
cout << v << " "; // 輸出該頂點
++count;
// 將所有v指向的頂點的入度減1，并將入度減為0的頂點入棧
list<int>::iterator beg = adj[v].begin();
for( ; beg!=adj[v].end(); ++beg)
if(!(--indegree[*beg]))
q.push(*beg); // 若入度為0，則入棧
}
if(count < V)
return false; // 沒有輸出全部頂點，有向圖中有回路
else
return true; // 拓撲排序成功
}
測試如下DAG圖：
int main()
{
Graph g(6); // 創(chuàng)建圖
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
g.topological_sort();
return 0;
}
輸出結果是 4, 5, 2, 0, 3, 1。這是該圖的拓撲排序序列之一。
每次在入度為0的集合中取頂點，并沒有特殊的取出規(guī)則，隨機取出也行，這里使用的queue。取頂點的順序不同會得到不同的拓撲排序序列，當然前提是該圖存在多個拓撲排序序列。
由于輸出每個頂點的同時還要刪除以它為起點的邊，故上述拓撲排序的時間復雜度為$O(V+E)$。
另外，拓撲排序還可以采用 深度優(yōu)先搜索（DFS）的思想來實現(xiàn)，詳見《topological sorting via DFS》。
