Vinn's Studio

Topological Sorting

Word count: 1kReading time: 4 min
2021/12/23 Share

拓扑排序问题的一般框架。

当题目中给出某个数组 arr，其中每个元素 arr[i] = [a, b] 表示 a 必须出现在 b 之前或 a 的某个值比 b 更大等相对关系时，可以考虑将 a, b, ... 看做看做节点，它们之间的相对关系看做有向边，构建有向无环图（Directed Acyclic Graph, DAG），然后通过拓扑排序解决问题。

拓扑排序

给定一个包含 n 个节点的有向图 G，如果它的节点编号的一种排列满足：

对于图 G 中的任意一条有向边 (u,v)，u 在该排列中都出现在 v 的前面。

那么称该排列是图 G 的「拓扑排序」。根据上述的定义，有以下两个结论：

  • 若图中存在环，则该图不可能有拓扑排序，因此能否拓扑排序可以用来简单地判断一张图中是否有环；
  • 有向无环图（DAG）的拓扑排序可能不止一种；

拓扑排序算法

LeetCode 210. 课程表 II 就是经典的拓扑排序问题，以此问题为例，拓扑排序主要有以下两种经典算法。

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi]，表示在选修课程 ai 前必须先选修 bi 。

  • 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回任意一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例：

1
2
3
4
输入：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] 。

kahn 算法：广度优先搜索

拓扑排序最经典的算法是 Kahn 算法。算法步骤为：

  1. 获取图中所有入度为 0 的点排在结果序列中，并在原图中将它们删除（则这些点指向的节点入度均会减少 1）；
  2. 重复上一步骤，直到所有点都被删除，返回结果序列即可（删除有向无环图的节点不会产生环，所以每时每刻都一定存在入度为 0 的点，一定可以不断进行下去，直到所有点被删除）；

注意：

  • 实际编程过程中，一般会使用一个队列动态地储存每个时刻所有入度为 0 的节点（而不是使用 while 循环来重复步骤 1）；
  • DAG 的拓扑排序结果不止一种，如果要求在符合拓扑结构的前提下，输出的序列要符合某种顺序（例如字典序），则可以改为用优先队列动态地储存每个时刻所有入度为 0 的节点；

LeetCode 210. 课程表 II 的具体解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import collections
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 存储有向图：edges[i] = [j,k,l] 表示节点 i 的领接表，即 i 分别指向节点 j,k,l
        edges = collections.defaultdict(list)
        # 存储每个节点的入度
        indeg = [0] * numCourses
        # 存储输出序列
        result = list()

        # 构建 DAG 并记录节点入度
        for info in prerequisites:
            edges[info[1]].append(info[0])
            indeg[info[0]] += 1
        
        # 将所有入度为 0 的节点放入队列中
        q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])

        # 开始拓扑排序
        while q:
            # 从队首取出一个节点
            u = q.popleft()
            # 放入答案中
            result.append(u)
            for v in edges[u]: # 对于 u 的每个领接节点
                indeg[v] -= 1
                # 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
                if indeg[v] == 0:
                    q.append(v)

        if len(result) != numCourses:
            result = list()
        return result

深度优先搜索

详见官方题解方法一

Author：Lingfeng Zhu

Original Link：https://lingfengzhu.github.io/2021/12/23/Topological-Sorting/

Published：December 23rd 2021, 2:17:17 pm

Updated：December 23rd 2021, 3:57:49 pm

Copyright：This Article Uses Attribution-NonCommercial 4.0 International as the license

CATALOG
  1. 拓扑排序
  2. 拓扑排序算法
    1. kahn 算法：广度优先搜索
    2. 深度优先搜索
Total : 33
2022
2021
2020
NLP Survival Analysis COVID-19 Conda Docker Python Hexo Web-Frontend Pytorch RecSys
Deep-Learning Algorithm Statistics Syntax Machine-Learning Finance