最近在看一些图算法，发现拓扑排序频繁出现，这里写一下自己的一些总结。

拓扑排序是对于有向无环图而言的 (DAG)，就是对于这个图所有的点 (V1, V2, … Vn) 找到一个点序列使得任意边 (u, v)，u 出现在 v 的前面。很容易证明，如果一个有向图中有环那么不存在拓扑排序。

现实中的问题

首先来看现实中哪些问题需要拓扑排序的，课程排序，编译依赖问题，类似的凡是涉及到相关顺序的时间安排，比如 Rails 里面的初始化调用了库Tsort来进行排序。Unix 中有个命令也叫tsort)，在有的 makefile 里面还直接使用了这个命令来解决依赖问题。

O(V+E) 的算法

topologicalsort

拓扑排序的基本算法是用 DFS，我们希望把有出度的点尽量排在前面，所以这里需要注意和 DFS 的区别。比如上面图中的一个 DFS 访问顺序是：5 2 3 1 0 4，但是这不是一个拓扑排序，4 需要排在 0 的前面，5, 4, 0, 2, 3, 1。
拓扑排序中需要等迭代完节点的连接邻点后再把当前点压入栈。

#include <iostream>
#include <stdio.h>
#include <list>
#include <stack>

using namespace std;

class Graph {
    int V;
    list<int>* adj;
    void _topological_sort(int v, bool visited[], stack<int>& stack);
public:
    Graph(int v);
    ~Graph();
    void addEdge(int v, int w);
    void Topological_sort();
};

Graph::Graph(int v):V(v) {
    adj = new list<int>[V];
}

Graph::~Graph() {
    delete [] adj;
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

void Graph::_topological_sort(int v, bool visited[], stack<int>& stack) {
    visited[v] = true;
    for(list<int>::iterator it = adj[v].begin(); it != adj[v].end(); ++it) {
        int u = *it;
        if(visited[u] == false)
            _topological_sort(u, visited, stack);
    }
    stack.push(v);
}

void Graph::Topological_sort() {
    bool visited[V];
    stack<int> stack;
    for(int i=0; i<V; i++)
        visited[i] = false;
    for(int i=V-1; i>=0; i--) {
        if(visited[i] == false) {
            _topological_sort(i, visited, stack);
        }
    }
    while(!stack.empty()) {
        int v = stack.top();
        stack.pop();
        std::cout << " " << v << " ";
    }
    std::cout << std::endl;
}

int main() {
    Graph g(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
    cout << "Following is topological sort result: \n";
    g.Topological_sort();
    return 0;
}

唯一性

如果一个 DAG 的拓扑排序中任意连续的两点都是可连通的，那么这个序列也就是 DAG 的 Hamiltonian 路径，而且如果 DAG 图的 Hamiltonian 路径存在，那么拓扑排序就是唯一的。否则如果一个拓扑排序结果不是 Hamiltonian 路径，那么就存在多个拓扑排序结果。

其他图算法的预处理

• DAG 的强连通分支问题
  先得到拓扑排序，形成逆向图 (所有边与原来方向相反)，然后根据拓扑排序依次再进行 DFS。

• DAG 的最短路径问题，这可以在 O(V+E) 复杂度解决最短路径问题。同样类似的算法适用与 DAG 的最长路径问题，给定一个点求 DAG 中的各个点与给定点之间的最长路径。最长路径问题要比最短路径问题难，因为最长路径问题没有最优子结构，对于通用的图的最长路径算法还是 NP 难的问题。