拓扑排序之Kahn算法

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

拓扑排序

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

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

1. 必须先吃饭，再睡觉
2. 必须先刷题，再睡觉

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

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

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

1. 顶点A 指向 顶点B
2. 顶点B 指向 顶点C
3. 顶点C 指向 顶点A

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

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

Kahn算法

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

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

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

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

实践

学习过程中要善于理论联系实际。故在介绍完拓扑排序的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;
    }

}

参考文献

1. 算法·第4版 Robert Sedgewick、Kevin Wayne著