力扣 210. 课程表 II

2026-05-01 暂无评论

全文共 385 字，阅读约 2 分钟

题目描述

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

请你返回一个可以修完所有课程的学习顺序。如果不可能完成所有课程（即存在环），返回一个空数组。

解题方法：拓扑排序（Kahn 算法）

本题是经典的拓扑排序问题。课程之间的先修关系构成一个有向图，需要找到一个拓扑序，使得对于每条有向边 bi -> ai，bi 在拓扑序中出现在 ai 之前。

算法思路

建图：使用邻接表 g 存储有向图，g[y] 表示所有以 y 为先修课的课程列表。
统计入度：in_edge[x] 记录课程 x 的入度（即有多少门先修课）。
初始化队列：将所有入度为 0 的课程（即没有先修课的课程）加入队列。
BFS 遍历：
- 从队列中取出一个课程 x，将其加入结果集。
- 遍历 x 的所有后继课程 y，将其入度减 1。
- 若 y 的入度变为 0，说明其所有先修课都已修完，将 y 加入队列。
判断是否有解：如果结果集中的课程数等于 numCourses，说明所有课程都可以修完；否则存在环，返回空数组。

代码解析

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 构建邻接表，g[y] 存储所有以 y 为先修课的课程
        g = [[] for _ in range(numCourses)]
        # 入度数组，in_edge[x] 表示课程 x 的入度
        in_edge = [0] * numCourses

        # 遍历先修关系，建图并统计入度
        for x, y in prerequisites:
            g[y].append(x)      # 添加有向边 y -> x
            in_edge[x] += 1      # 课程 x 的入度加 1

        ans = []
        # 将所有入度为 0 的课程加入队列（即不需要先修课的课程）
        q = deque(i for i in range(numCourses) if in_edge[i] == 0)

        # BFS 拓扑排序
        while q:
            x = q.popleft()      # 取出一个入度为 0 的课程
            ans.append(x)        # 将其加入学习顺序

            # 遍历当前课程的所有后继课程
            for y in g[x]:
                in_edge[y] -= 1  # 后继课程的先修课要求减 1
                if in_edge[y] == 0:
                    q.append(y)  # 入度变为 0，加入队列

        # 如果学完的课程数少于总课程数，说明存在环
        if len(ans) < numCourses:
            return []            # 无法学完所有课程

        return ans               # 返回拓扑序列