Course Schedule

207. 课程表

分析

构建图结构与入度数组
- 使用邻接表 g 表示课程之间的依赖关系：对于 prerequisites[i] = [a, b]，将 b -> a 加入图中
- 使用入度数组 d 记录每个课程的入度（依赖它的先修课程数量）
初始化队列
- 将入度为 0 的课程（无依赖课程）加入队列 q，这些课程可以直接开始学习
拓扑排序
- 从队列中取出课程，计数器 res 加 1（表示完成了一门课程）
- 遍历该课程的邻接课程，将它们的入度减 1。如果某门课程的入度减为 0，将其加入队列
- 重复直到队列为空
判断是否可行
- 如果最终完成课程数 res 等于 numCourses，说明可以完成所有课程，返回 true
- 否则返回 false，表示存在环形依赖，课程无法全部完成

时间复杂度

构建图：遍历所有的先修课程关系，时间复杂度为 O(E)，其中 E 是先修课程的数量
拓扑排序：每门课程和它的邻接课程都最多被访问一次，时间复杂度为 O(V)，其中 V 是课程数

总时间复杂度 O(E + V)

空间复杂度

图邻接表 g 占用 O(E) 空间
入度数组 d 占用 O(V) 空间。
队列 q 的最大空间占用为 O(V)

空间复杂度为 O(E + V)

C++代码

 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
34
35
36


class Solution
{
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        // 1. 构建图和入度数组
        std::vector<std::vector<int>> g(numCourses); // 邻接表
        std::vector<int> d(numCourses);             // 入度数组
        for (std::vector<int>& pre : prerequisites) {
            g[pre[1]].push_back(pre[0]); // 构建图：b -> a
            ++d[pre[0]];                 // 课程 a 的入度加 1
        }

        // 2. 初始化队列
        std::queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (d[i] == 0)               // 入度为 0 的课程入队
                q.push(i);
        }

        // 3. 拓扑排序
        int res = 0;                    // 记录完成课程数量
        while (!q.empty()) {
            ++res;                      // 每完成一门课程，计数加 1
            int i = q.front();
            q.pop();
            for (int j : g[i]) {        // 遍历当前课程的后续课程
                if (--d[j] == 0)        // 后续课程入度减 1
                    q.push(j);          // 如果入度变为 0，加入队列
            }
        }

        // 4. 判断结果
        return res == numCourses;       // 如果完成课程数等于总课程数，返回 true
    }
};