本文介绍如何利用Kahn算法解决有向无环图DAG中的Topological Sorting拓扑排序问题

拓扑排序

所谓 Topological Sorting 拓扑排序，指的是对于一个有向图而言，我们对所有顶点进行线性排序。要求对于有向图中任意一条由顶点u指向顶点v的边而言，排序结果中顶点u必须排在顶点v的前面。简单来说，拓扑排序就是将某集合上的偏序关系转换为该集合上的全序关系

事实上，拓扑排序在现实中非常常见。例如，我们一天需要做三件事：吃饭、睡觉、刷题。而这些事情的需要遵从下述的偏序关系：

必须先吃饭，再睡觉
必须先刷题，再睡觉

按照上述偏序关系的要求，我们该如何安排这一天呢？显然对于吃饭、刷题而言，二者并无偏序关系，故这二者谁先谁后均是符合要求的。故我们下面两种拓扑排序的结果都是正确的

吃饭、刷题、睡觉
刷题、吃饭、睡觉

同时对于一个有向图而言，存在拓扑排序的前提是：该图是一个有向无环图（DAG, Directed Acyclic Graph）。例如一个有向图中存在下述的有向边：

顶点A 指向顶点B
顶点B 指向顶点C
顶点C 指向顶点A

由于顶点A、顶点B、顶点C间构成了环，故下述的排序结果均不符合拓扑排序要求

顶点A、顶点B、顶点C
顶点B、顶点C、顶点A

Kahn算法

在一个有向图中，一个顶点的出度指的是由该顶点指出的边的总数；一个顶点的入度为指向该顶点的边的总数

该算法的核心思路很简单：当一个顶点A的入度为0时，则说明顶点A此时没有任何的顶点可以排在它前面了。故我们就可以将顶点A从图中移除，并将其追加到排序结果后面；同时随着顶点A从图中移除，由它指出的有向边也将同时被删除，故而会导致图中相应顶点的入度也会减少。当图中某顶点的入度减到0时，重复上述步骤即可；最后，当排序结果中顶点的数量等于有向图的顶点总数，则说明排序结果即为该有向图的拓扑排序结果；反之，如果排序结果中顶点的数量小于有向图的顶点总数，即排序结果未包含所有顶点。则说明该有向图中存在环，不是一个有向无环图DAG

从上不难看出，Kahn算法不仅可以帮助我们方便地给出有向图拓扑排序的结果；还可以帮助我们判定一个有向图是否为一个有向无环图。该算法基本步骤如下所示：

统计每个顶点的入度，统计每个顶点指出的边的终点集合
遍历顶点的入度统计结果，将入度为0的顶点全部加入队列
遍历从队列头部移出的顶点
对于移出队列头部的顶点而言，先将其追加到排序结果当中；然后，对所有以该顶点为起点的边的终点而言，将其入度均减1。如果入度减为0，则将相应顶点加入队列当中
重复步骤3～4，直到队列为空为止
判定排序结果中顶点的数量是否等于有向图的顶点总数

实践

学习过程中要善于理论联系实际。故在介绍完拓扑排序的Kahn算法后，现在我们来进行实践。这里以LeetCode的第210题——课程表 II 为例

❝

现在你总共有numCourses门课需要选，记为0到numCourses-1。给你一个数组prerequisites，其中prerequisites[i] = [ai, bi]，表示在选修课程ai前必须先选修bi。例如，想要学习课程0，你需要先完成课程1，我们用一个匹配来表示：[0,1]。返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回任意一种就可以了。如果不可能完成所有课程，返回一个空数组

❝

示例 1

输入：numCourses = 2, prerequisites = [[1,0]]

输出：[0,1]

解释：总共有2门课程。要学习课程1，你需要先完成课程0。因此，正确的课程顺序为[0,1]

❝

示例 2

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

输出：[0,2,1,3]

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

❝

示例 3

输入：numCourses = 1, prerequisites = []

输出：[0]

❝

提示

1 <= numCourses <= 2000

0 <= prerequisites.length <= numCourses * (numCourses – 1)

prerequisites[i].length == 2

0 <= ai, bi < numCourses

ai != bi

所有[ai, bi] 互不相同

故利用Kahn算法我们不难通过Java实现，代码如下所示

/**
 * 基于Kahn算法的拓扑排序
 */
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // Key: 有向边的起点；Value: 以Key为起点的所有有向边的终点集合
        Map<Integer, Set<Integer>> edges = new HashMap<>();
        // 各顶点的入度
        int[] indge = new int[numCourses];

        for (int[] edge : prerequisites) {
            int start = edge[1];    // 有向边的起点
            int end = edge[0];      // 有向边的终点
            // 记录有向图的边
            edges.computeIfAbsent(start, HashSet::new).add( end );
            // 统计各顶点的入度
            indge[end]++;
        }

        // 将所有入度为0的顶点 加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i=0; i<numCourses; i++) {
            if( indge[i]==0 ) {
                queue.offer(i);
            }
        }

        List<Integer> sortRes = new ArrayList<>(); // 拓扑排序结果
        while (!queue.isEmpty()) {
            // 入度为0的顶点可安全从有向图中删除, 同时加入拓扑排序的结果
            int node = queue.poll();
            sortRes.add(node);
            // 对于以该顶点为起点的所有边而言，从有向图中删除该顶点后，
            // 相应边同时被删除，故相应边终点的入度也会减少1
            for (Integer end : edges.getOrDefault(node, Collections.emptySet()) ){
                indge[end]--;
                // 对于入度减为0的顶点而言，说明其后续可以安全地从图中删除，故加入队列
                if( indge[end]==0 ) {
                    queue.offer(end);
                }
            }
        }

        int[] res = new int[0];
        // 拓扑排序的结果中包含所有顶点，则说明成功
        // 反之，拓扑排序的结果中未包含所有顶点，则该有向图中存在环，即失败
        if( sortRes.size() == numCourses ) {
            res = sortRes.stream()
                .mapToInt(Integer::valueOf)
                .toArray();
        }
        return res;
    }

}