在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件:

• 每个顶点出现且只出现一次。
• 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
  在有向无环图（DAG）中才有拓扑排序，非DAG图没有拓扑排序一说。

算法过程

拓扑排序的实现过程非常简单：在每个时刻，挑选出当前入度为0的节点加入到结果序列中，并删除当前顶点所有关联的边。如果当前时刻，存在多个入度为0的节点，随机挑选一个即可。因此拓扑排序的结果可能不唯一，但是一定会满足上述关于拓扑排序的两个必要条件。因此算法大致过程如下：

1. 初始化结果序列S为空。执行步骤2.
2. 如果图中的顶点数为0，或没有入度为0的顶点，算法结束，返回S。否则执行步骤2.
3. 挑选出当前轮次中入度为0的顶点，如果有多个，随机挑选一个，执行步骤3.
4. 将步骤2中挑选出的顶点加入到结果序列中，并删除当前顶点和当前顶点关联的边。然后执行步骤1.
   在DAG图中，当算法停止时，我们可以得到当前DAG图的一个拓扑排序结果S。下面我们用一个简单的例子演示拓扑排序的过程。

以上就是拓扑排序的全部内容，下面我们以剑指 Offer II 113. 课程顺序为例，展示拓扑排序的详细过程，代码如下。

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 存储有向图
        List<Integer> []edges = new ArrayList[numCourses];
        // 存储每个节点的入度
        int[] in_degree = new int[numCourses];
        // 存储答案
        int[] result = new int[numCourses];

        //初始化邻接链表
        for (int i = 0; i < numCourses; ++i) {
            edges[i] = new ArrayList<>();
        }

        //构建邻接链表，统计每个顶点的入度
        for (int[] info : prerequisites) {
            edges[info[1]].add(info[0]);
            ++in_degree[info[0]];
        }
        Queue<Integer> queue = new LinkedList<>();

        // 将所有入度为 0 的节点放入队列中
        for (int i = 0; i < numCourses; ++i) {
            if (in_degree[i] == 0) {
                queue.offer(i);
            }
        }

        int index = 0;
        while (!queue.isEmpty()) {
            // 从队首取出一个节点
            int u = queue.poll();
            // 放入答案中
            result[index++] = u;
            for (int v: edges[u]) {
                --in_degree[v];
                // 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
                if (in_degree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        //如果不可能完成所有课程，返回一个空数组
        return index != numCourses ? new int[0] : result;
    }