拓扑排序

拓扑排序是图论中的一个概念，主要应用于有向图。它的目的是对图中的顶点进行线性排序，使得对于任何从顶点 \(u\) 到顶点 \(v\) 的有向边，\(u\) 在排序中都出现在 \(v\) 之前。这种排序特别适用于解决表示“先决条件”关系的问题，如任务调度、课程规划等场景。

一个常用的算法是 Kahn 算法，其步骤如下：

1. 计算图中所有顶点的入度。
2. 将所有入度为 0 的顶点放入一个队列中。
3. 当队列非空时，执行以下操作：
   • 从队列中移除一个顶点 \(u\)，并将其加入到排序结果中。
   • 遍历从 \(u\) 出发的所有边 \(u \rightarrow v\)，将每个相邻顶点 \(v\) 的入度减 1。
   • 如果某个相邻顶点 \(v\) 的入度变为 0，则将 \(v\) 加入队列。
4. 重复步骤 3，直到队列为空。
5. 如果排序结果中的顶点数量与图中的顶点总数相同，则图不存在环，否则图中存在环，无法进行拓扑排序。我们可以使用拓扑排序判断图是否有环。

例子

210. 课程表 II - 力扣（LeetCode）。

Python中存储图最简单的方式是collections.defaultdict(list)。

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 存储有向图
        edges = collections.defaultdict(list)
        # 存储每个节点的入度
        indeg = [0] * numCourses
        # 存储答案
        result = list()

        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]:
                indeg[v] -= 1
                # 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
                if indeg[v] == 0:
                    q.append(v)

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

# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/course-schedule-ii/solutions/249149/ke-cheng-biao-ii-by-leetcode-solution/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。