拓撲排序的英文名是 Topological sorting。拓撲排序要解決的問題是給一個圖的所有節(jié)點排序。

一、什么是拓撲排序

在圖論中，拓撲排序（Topological Sorting）是一個有向無環(huán)圖（DAG, Directed Acyclic Graph）的所有頂點的線性序列。且該序列必須滿足下面兩個條件：

（1）每個頂點出現(xiàn)且只出現(xiàn)一次。

（2）若存在一條從頂點 A 到頂點 B 的路徑，那么在序列中頂點 A 出現(xiàn)在頂點 B 的前面。

有向無環(huán)圖（DAG）才有拓撲排序，非DAG圖沒有拓撲排序一說。

例如，下面這個圖：

它是一個 DAG 圖，那么如何寫出它的拓撲排序呢？這里說一種比較常用的方法：

（1）從 DAG 圖中選擇一個 沒有前驅（即入度為0）的頂點并輸出。

（2）從圖中刪除該頂點和所有以它為起點的有向邊。

（3）重復 1 和 2 直到當前的 DAG 圖為空或當前圖中不存在無前驅的頂點為止。后一種情況說明有向圖中必然存在環(huán)。

于是，得到拓撲排序后的結果是 { 1, 2, 4, 3, 5 }。

通常，一個有向無環(huán)圖可以有一個或多個拓撲排序序列。

二、拓撲排序的應用

拓撲排序通常用來“排序”具有依賴關系的任務。

比如，如果用一個DAG圖來表示一個工程，其中每個頂點表示工程中的一個任務，用有向邊表示在做任務 B 之前必須先完成任務 A。故在這個工程中，任意兩個任務要么具有確定的先后關系，要么是沒有關系，絕對不存在互相矛盾的關系（即環(huán)路）。

三、拓撲排序的實現(xiàn)

根據(jù)上面講的方法，我們關鍵是要維護一個入度為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ù)，記錄當前已經(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;            // 拓撲排序成功
}

測試如下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)。