拓扑排序

基本思想
拓扑排序应用的场合不再是一个简单的数组，而是研究图论里面顶点和顶点连线之间的性质。拓扑排序就是要将这些顶点按照相连的性质进行排序。拓扑排序一般用来理清具有依赖关系的任务。

实现

• 将问题用一个有向无环图（DAG, Directed Acyclic Graph）进行抽象表达，定义出哪些是图的顶点，顶点之间如何互相关联。
• 可以利用广度优先搜索或深度优先搜索来进行拓扑排序。

Leetcode题目

• Leetcode 207. 课程表
• Leetcode 210. 课程表 II

课程表 II 解题

题目

现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例:

输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
     因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

步骤

1、设定顶点（节点）变量个数，和个数之间的路线关系（用二维数组保存）
2、使用一个一维数组用来记录顶点（节点）入度的数量
3、设置一个队列，把入度为0的数放入队列
4、设置一个一维数组用于保存返回值，取出队列元素放到一维数组，并修改其他节点的入度数量。
5、返回

Java代码

public int[] topologicalSort(int numCourses, int[][] prerequisites) {
    // 用于保存节点入度
    int[] in = new int[numCourses];
    // 响应结果
    int[] res = new int[numCourses];
    // 队列，用于保存入度为0的结点
    Queue<Integer> queue = new LinkedList<>();
    // 统计节点的入度
    for (int[] edge: prerequisites) {
        in[edge[0]]++;
    }
    // 把入度为0的结点放入队列
    for (int i = 0; i < numCourses; i++) {
        if (in[i] == 0) {
            queue.offer(i);
        }
    }
    // 返回值索引
    int index = 0;
    // 当有入度为0时，执行
    while (!queue.isEmpty()) {
        Integer tmp = queue.poll();
        res[index++] = tmp;
        for (int[] edge : prerequisites) {
            if (edge[1] == tmp) {
                // 减少入度个数
                in[edge[0]]--;
                // 入度为0，放入队列中
                if (in[edge[0]] == 0) {
                    queue.offer(edge[0]);
                }
            }
        }
    }
    // 如果出现环了，入度没有0的结点
    if (index  != numCourses) {
        return new int[]{};
    }
    return res;
}

END!