什么是拓扑排序

简单的说拓扑排序(Topological sorting)就是给一个有向无环图的所有节点排序。 序列中每个顶点出现且只出现一次，若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

性质

• 能 拓扑排序 的图，一定是有向无环图；（当然无向图也可以利用同样的思路判断是否存在环）
• 有向无环图，一定能拓扑排序；
• 拓扑排序不唯一；
• 拓扑排序的时间复杂度是 $O(V+E)$，其中 $V$ 是顶点数，$E$ 是边数。

拓扑排序的应用

拓扑排序通常用来 排序 具有依赖关系的任务。

拓扑排序可以判断图中是否有环（是否能够构造拓扑排序），还可以用来判断图是否是一条链。拓扑排序可以用来求 AOE 网中的关键路径，估算工程完成的最短时间。

构造拓扑序列步骤

1. 从图中选择一个入度为零的点。
2. 输出该顶点，从图中删除此顶点及其所有的出边。

重复上面两步，直到所有顶点都输出，拓扑排序完成，或者 图中不存在入度为零的点，此时说明图是有环图，拓扑排序无法完成。

拓扑排序的实现

常用两种实现方式：Kahn 算法和 DFS 算法。

Kahn 算法

Kahn 算法就是通过维护一个入度为 0 的点的集合，每次从集合中取出一个点，然后删除该点及其所有的出边，重复这个过程直到所有的点都被删除或者集合为空，如果所有的点都被删除，那么拓扑排序完成，否则图中存在环。
使用队列维护入度为 0 的节点，对每个队列中的元素，将出边对应的终点入度减 1，若减后为 0，加入队列。

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //存储某个节点能够到达的其他节点集合
        List<Integer>[] lists = new ArrayList[numCourses];

        //记录某个节点的入度
        int[] points = new int[numCourses];

        for(int[] p : prerequisites){
            points[p[0]]++;
            if(lists[p[1]] == null){
                lists[p[1]] = new ArrayList<>();
            }
            lists[p[1]].add(p[0]);
        }

        Queue<Integer> queue = new LinkedList<>();
        //找到入度为 0 的节点

        for(int i = 0; i < numCourses; i++){
            //入度为 0，添加到队列中
            if(points[i] == 0){
                queue.add(i);
            }
        }

        //记录遍历的课程顺序
        int[] res = new int[numCourses];
        int idx = 0;

        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-- > 0){
                int p = queue.poll();
                res[idx++] = p;
                List<Integer> list = lists[p];
                if(list == null){
                    continue;
                }
                for(int val : list){
                    points[val]--;
                    if(points[val] == 0){
                        queue.add(val);
                    }
                }
            }
        }

        //idx == numCourses 意味着全部课程都访问过了，即最终都能够满足 0 入度的条件
        return idx == numCourses ? res : new int[0];
    }
}

DFS 算法

关于 DFS 算法的理解，可以看 210. 课程表 II 官方题解 中的动图理解。

class Solution {
    // 存储有向图
    List<List<Integer>> edges;
    // 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
    int[] visited;
    // 用数组来模拟栈，下标 n-1 为栈底，0 为栈顶
    int[] result;
    // 判断有向图中是否有环
    boolean valid = true;
    // 栈下标
    int index;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 初始化
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[numCourses];
        result = new int[numCourses];
        index = numCourses - 1;

        // 有向图的邻接表存储
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }

        // 每次挑选一个「未搜索」的节点，开始进行深度优先搜索
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        
        if (!valid) {
            return new int[0];
        }
        // 如果没有环，那么就有拓扑排序
        return result;
    }

    public void dfs(int u) {
        // 将节点标记为「搜索中」
        visited[u] = 1;
        // 搜索其相邻节点
        // 只要发现有环，立刻停止搜索
        for (int v: edges.get(u)) {
            // 如果「未搜索」那么搜索相邻节点
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            }
            // 如果「搜索中」说明找到了环
            else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        // 将节点标记为「已完成」
        visited[u] = 2;
        // 将节点入栈
        result[index--] = u;
    }
}

参考

• 什么是拓扑排序
• OI wiki：拓扑排序