(文章引用于http://songlee24.github.io/2015/05/07/topological-sorting/）
一熟呛、什么是拓?fù)渑判?/strong>
在圖論中静檬，拓?fù)渑判颍═opological Sorting）是一個有向無環(huán)圖（DAG, Directed Acyclic Graph）的所有頂點的線性序列炭懊。且該序列必須滿足下面兩個條件：
- 每個頂點出現(xiàn)且只出現(xiàn)一次。
- 若存在一條從頂點 A 到頂點 B 的路徑拂檩，那么在序列中頂點 A 出現(xiàn)在頂點 B 的前面侮腹。
有向無環(huán)圖（DAG）才有拓?fù)渑判颍荄AG圖沒有拓?fù)渑判蛞徽f稻励。
例如父阻，下面這個圖：
它是一個 DAG 圖，那么如何寫出它的拓?fù)渑判蚰赝椋窟@里說一種比較常用的方法：
- 從 DAG 圖中選擇一個 沒有前驅(qū)（即入度為0）的頂點并輸出加矛。
- 從圖中刪除該頂點和所有以它為起點的有向邊。
- 重復(fù) 1 和 2 直到當(dāng)前的 DAG 圖為空或當(dāng)前圖中不存在無前驅(qū)的頂點為止煤篙。后一種情況說明有向圖中必然存在環(huán)斟览。
于是，得到拓?fù)渑判蚝蟮慕Y(jié)果是 { 1, 2, 4, 3, 5 }舰蟆。
通常趣惠，一個有向無環(huán)圖可以有一個或多個拓?fù)渑判蛐蛄小?/p>
二、拓?fù)渑判虻膽?yīng)用
拓?fù)渑判蛲ǔＳ脕怼芭判颉本哂幸蕾囮P(guān)系的任務(wù)身害。
比如味悄，如果用一個DAG圖來表示一個工程，其中每個頂點表示工程中的一個任務(wù)塌鸯，用有向邊 表示在做任務(wù) B 之前必須先完成任務(wù) A侍瑟。故在這個工程中，任意兩個任務(wù)要么具有確定的先后關(guān)系，要么是沒有關(guān)系涨颜，絕對不存在互相矛盾的關(guān)系（即環(huán)路）费韭。
三、拓?fù)渑判虻膶崿F(xiàn)
根據(jù)上面講的方法庭瑰，我們關(guān)鍵是要維護(hù)一個入度為0的頂點的集合星持。
圖的存儲方式有兩種：鄰接矩陣和鄰接表。這里我們采用鄰接表來存儲圖弹灭，C++代碼如下：
#include<iostream>
#include <list>
#include <queue>
using namespace std;
/************************類聲明************************/
class Graph
{
int V; // 頂點個數(shù)
list<int> *adj; // 鄰接表
queue<int> q; // 維護(hù)一個入度為0的頂點的集合
int* indegree; // 記錄每個頂點的入度
public:
Graph(int V); // 構(gòu)造函數(shù)
~Graph(); // 析構(gòu)函數(shù)
void addEdge(int v, int w); // 添加邊
bool topological_sort(); // 拓?fù)渑判?};
/************************類定義************************/
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ù)督暂，記錄當(dāng)前已經(jīng)輸出的頂點數(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; // 拓?fù)渑判虺晒?}
測試如下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;
}
輸出結(jié)果是 4, 5, 2, 0, 3, 1。這是該圖的拓?fù)渑判蛐蛄兄弧?/p>
每次在入度為0的集合中取頂點捡鱼，并沒有特殊的取出規(guī)則八回，隨機(jī)取出也行，這里使用的queue驾诈。取頂點的順序不同會得到不同的拓?fù)渑判蛐蛄胁纾?dāng)然前提是該圖存在多個拓?fù)渑判蛐蛄小?/p>
由于輸出每個頂點的同時還要刪除以它為起點的邊，故上述拓?fù)渑判虻臅r間復(fù)雜度為$O(V+E)$翘鸭。
另外滴铅，拓?fù)渑判蜻€可以采用 深度優(yōu)先搜索（DFS）的思想來實現(xiàn)，詳見《topological sorting via DFS》就乓。
