LeetCode 210. Course Schedule II

Posted on In Views:
LeetCode exercise

210. Course Schedule II

解题思路

题目解析： 我们需要找到一个可以完成所有课程的顺序，若无法完成所有课程，则返回空列表。这本质上是一个 有向图的拓扑排序 问题。

思路

  1. 构建图 (邻接表)：
    • 课程是图的节点，每个 prerequisites[i] = [a, b] 表示修 a 之前必须修 b，因此 b → a 是一条有向边。
    • 使用 邻接表 记录图，并维护每个课程的 入度（被指向的次数）。
  2. 拓扑排序 (Kahn’s Algorithm, BFS)：
    • 找到所有 入度为 0 的课程，作为起点放入队列。
    • 每次从队列取出一个课程，将它加入结果列表，并将它指向的课程的入度减 1。
    • 如果某个课程的入度减为 0，加入队列。
    • 若最终无法完成所有课程（结果列表长度小于 numCourses），说明存在 环，返回空列表。
  3. 时间复杂度分析：
    • 构建图 需要遍历 prerequisites，时间复杂度 O(E) (E 是先修关系的数量)。
    • 拓扑排序 需要遍历所有课程 O(V)，再处理每条边一次 O(E)，所以总时间复杂度为 O(V + E)，适用于稀疏图。

代码实现 (Python, BFS)

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
from collections import deque
from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 1. 构建图 (邻接表) 和 计算入度
        adj_list = {i: [] for i in range(numCourses)}
        in_degree = [0] * numCourses
        
        for course, pre in prerequisites:
            adj_list[pre].append(course)
            in_degree[course] += 1
        
        # 2. 找到所有入度为 0 的课程，加入队列
        queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
        order = []
        
        # 3. 拓扑排序 (BFS)
        while queue:
            course = queue.popleft()
            order.append(course)
            
            for neighbor in adj_list[course]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
        
        # 4. 如果最终排序包含所有课程，返回结果，否则返回空列表
        return order if len(order) == numCourses else []

代码解析

Step 1: 构建邻接表

1
2
adj_list = {i: [] for i in range(numCourses)}
in_degree = [0] * numCourses
  • adj_list 记录每个课程的后继课程（出边）。
  • in_degree[i] 记录课程 i 被指向的次数。

Step 2: 遍历 prerequisites，构建图

1
2
3
for course, pre in prerequisites:
    adj_list[pre].append(course)  # 先修课 pre 指向 course
    in_degree[course] += 1  # 课程 course 的入度增加

示例: 输入： 

1
2
numCourses = 4
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
构建的邻接表： 
1
2
3
4
0 → [1, 2]
1 → [3]
2 → [3]
3 → []
入度表： 
1
in_degree = [0, 1, 1, 2]

Step 3: 初始化队列

1
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])

入度为 0 的课程可以直接开始学习，加入队列。

初始队列： 

1
queue = [0]

Step 4: 拓扑排序 (BFS)

1
2
3
4
5
6
7
8
while queue:
    course = queue.popleft()
    order.append(course)

    for neighbor in adj_list[course]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)
  • 从 queue 取出一个课程 course，加入结果 order。
  • 遍历 course 指向的课程 neighbor，它的 in_degree 减 1。
  • 如果 neighbor 入度变为 0，加入 queue。

Step 5: 判断是否有环

1
return order if len(order) == numCourses else []
  • 如果 order 的长度等于 numCourses，返回 order。
  • 否则，说明有环，返回 []。

示例运行

示例 1

1
2
sol = Solution()
print(sol.findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

输出 

1
[0, 1, 2, 3]  # 或 [0, 2, 1, 3]

示例 2 (有环)

1
print(sol.findOrder(2, [[1,0],[0,1]]))

输出 

1
[]  # 由于 0 依赖 1，1 依赖 0，无法完成所有课程

时间 & 空间复杂度

  • 时间复杂度：O(V + E)，遍历 numCourses (V) + 遍历 prerequisites (E)。
  • 空间复杂度：O(V + E)，邻接表存储 E 条边，入度表存储 V 个课程。

扩展 (DFS 方法)

除了 BFS，还可以用 DFS 来解决，核心是： - 采用 递归 进行 深度优先搜索，检测 环。 - 维护一个 访问状态数组： - 0: 未访问 - 1: 访问中 (检测环) - 2: 访问完毕 (拓扑排序) - 递归构建拓扑排序的逆序结果。

DFS 代码： 

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
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        from collections import defaultdict

        graph = defaultdict(list)
        for course, pre in prerequisites:
            graph[pre].append(course)

        visited = [0] * numCourses
        order = []

        def dfs(course):
            if visited[course] == 1:  # 发现环
                return False
            if visited[course] == 2:  # 已经处理过
                return True

            visited[course] = 1
            for neighbor in graph[course]:
                if not dfs(neighbor):
                    return False
            
            visited[course] = 2
            order.append(course)
            return True

        for i in range(numCourses):
            if visited[i] == 0:
                if not dfs(i):
                    return []

        return order[::-1]  # 逆序输出
DFS 方法时间复杂度也是 O(V + E)，但更适合 递归结构 的问题。

总结

✅ BFS (拓扑排序)：

  • 适用于 Kahn's Algorithm
  • 代码简洁、直观

✅ DFS (递归检测环 + 逆序遍历)：

  • 适用于 递归场景
  • 需要额外的 访问状态数组

BFS 方法是 最直观且易于理解的，建议优先使用！🚀