1. 拓扑排序定义
2. 利用“DAG必有零入度顶点”的特性，实现拓扑排序
3. 基于DFS搜索的拓扑排序

1. 拓扑排序定义

将一个有向图无环图（DAG）的所有顶点排成一个线性序列，若该线性序列满足：每一个顶点都不会通过边，指向其在此序列中的前驱顶点，则该线性序列称为该图的一个拓扑排序。(注意：有向无环图是拓扑排序存在的充分必要条件）

以数据结构学习路线这一实际问题为例。首先，将数据结构相关知识点之间的依赖关系整理为一个有向无环图，如图1(a)所示。那么如何将这些知识点串联为一份学习计划，以保证在学习过程中，每次学习的知识点均在此前已学习过呢？这个问题可以用拓扑排序解决。

图1.拓扑排序

2. 利用“DAG必有零入度顶点”的特性，实现拓扑排序

在任一有向无环图中，必然存在入度为0的顶点。否则，每个顶点都至少有一条入边，这意味着包含环路。

于是该算法的描述如下：

1. 将入度为0的顶点m（及其关联边）从图G中取出，则剩余的G'依然是有向无环图。
2. 重新考量图G'，重复1步骤，直到所有顶点均被取出。
3. 对于每一个取出的顶点m，按取出的先后顺序排列，即构成了G的拓扑排序。

整个过程如图2所示：

图2.利用“DAG必有零入度顶点”的特性，实现拓扑排序

该算法的Java实现如下：（部分代码，其余代码可参考《图基础知识整理和代码实现》）

public void tSort() {
    while (n > 0){
        for(int j = 0; j < n; ++j){
            Vertex<Tv> vertex = V.get(j);
            if(vertex.getInDegree() == 0){
                System.out.print(remove(vertex.getData()));
                break;
            }
         }
    }
}

该算法的缺点是，不能判断图是否为DAG图，如果不是DAG图，会陷入死循环，改进方法是采用另外一种策略。

3. 基于DFS搜索的拓扑排序

在任一有向无环图中，必然存在出度为0的顶点。否则，每个顶点都至少有一条出边，这意味着包含环路。

在对有向无环图的DFS搜索中，首先因访问完成而转换至VISITED状态的顶点m，其出度必然为0。

基于上述两条特性，我们可以得出结论：

DFS搜索过程中各顶点被标记为VISITED的次序，恰好（按逆序）给出了原图的一个拓扑排序。

所以，基于DFS搜索算法，我们可以实现拓扑排序算法如下：

public Stack<Vertex<Tv>> tSort(Tv data) {
    Integer i = hashMap.get(data);
    if(i == null) return null;
    reset();
    AtomicInteger clock = new AtomicInteger(0);
    int v = i; Stack<Vertex<Tv>> stack = new Stack<Vertex<Tv>>();
    do {
        if(VStatus.UNDISCOVERED == status(v)) {
            if(!TSort(v,clock,stack)) {
                while (!stack.empty()) stack.pop();
                break;
            }
        }
    }while (i!=(v=(++v%n)));
    return stack;
}
private boolean TSort(int i, AtomicInteger clock, Stack<Vertex<Tv>> stack) {
    Vertex<Tv> vertex = V.get(i);
    vertex.setdTime(clock.addAndGet(1));
    vertex.setStatus(VStatus.DISCOVERED);
    for(int j = firstNeighbor(i); j > -1; j = nextNeighbor(i,j)){
        if(status(j) == VStatus.UNDISCOVERED){
            V.get(j).setParent(i);
            E.get(i).get(j).setType(EType.TREE);
            if(!TSort(j,clock,stack)) return false;
        }else if (status(j) == VStatus.DISCOVERED){
            E.get(i).get(j).setType(EType.BACKWARD);
            return false;
        }else {
            E.get(i).get(j).setType(dTime(i)<dTime(j)?EType.FORWARD:EType.CROSS);
        }
    }
    vertex.setStatus(VStatus.VISITED);
    stack.push(vertex); //最后访问的顶点
    return true;
}

该算法利用了《图基础知识整理和代码实现》中介绍的深度优先搜索算法框架，将顶点按VISITED的先后顺序入栈，这样在算法结束后，栈中至顶而下构成的序列即图的拓扑排序。而且，该算法可以判断该图是否是一个DAG图，如果不是DAG图，则必然存在后向边（BACKWARD），那么算法将提前结束，堆栈会被清空。