课程表 - Stellar Observer Protocol

799 字

4 分钟

课程表

2025-08-07

Algorithms

深度优先搜索

/

广度优先搜索

/

图

/

拓扑排序

题目描述#

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

解题思路#

建图：将课程依赖关系转化为有向图（邻接表）
统计入度：记录每个节点的入度数（前置课程数）
BFS初始化：所有入度为0的课程入队（可直接学习的课程）
拓扑排序：
- 出队课程，减少相邻节点入度
- 若相邻节点入度归零则入队
验证结果：若处理课程数=总课程数 → 可完成

关键洞察#

环检测：若存在环则拓扑排序无法完成（队列提前空）
BFS核心：入度为零的课程代表当前可学，是拓扑排序的起点，是拓扑排序的起点
贪心思想：总是优先处理无依赖的课程
图建模：将课程依赖抽象为有向边（如[1,0]表示0→1的边）

复杂度分析#

时间复杂度：O(V+E)
- 建图O(E) + BFS遍历所有节点和边O(V+E)
空间复杂度：O(V+E)
- 邻接表O(E) + 入度数组O(V) + 队列O(V)

代码实现#

递归版本

1
/**
2
 * @param {number} numCourses
3
 * @param {number[][]} prerequisites
4
 * @return {boolean}
5
 */
6
var canFinish = function (numCourses, prerequisites) {
7
    const edges = Array.from({
8
        length: numCourses
9
    }, () => []);
10
    for (const [a, b] of prerequisites) {
11
        edges[b].push(a);
12
    }
13
    const visited = new Array(numCourses).fill(0);
14
    const dfs = (u) => {
15
        visited[u] = 1;
16
        for (const v of edges[u]) {
17
            if (visited[v] === 0) {
18
                if (!dfs(v)) return false;
19
            } else if (visited[v] === 1) {
20
                return false;
21
            }
22
        }
23
        visited[u] = 2;
24
        return true;
25
    }
26
    for (let i = 0; i < numCourses; i++) {
27
        if (visited[i] === 0) {
28
            if (!dfs(i)) return false;
29
        }
30
    }
31
    return true;
32
};

迭代版本

1
const canFinish = (numCourses, prerequisites) => {
2
    // 1. 初始化图和入度数组
3
    const graph = Array.from({ length: numCourses }, () => []);
4
    const inDegree = new Array(numCourses).fill(0);
5

6
    // 2. 构建图结构并计算入度
7
    for (const [course, prereq] of prerequisites) {
8
        graph[prereq].push(course);  // 前置课程→当前课程的边
9
        inDegree[course]++;           // 当前课程入度+1
10
    }
11

12
    // 3. 初始化队列（入度为0的节点）
13
    const queue = [];
14
    for (let i = 0; i < numCourses; i++) {
15
        if (inDegree[i] === 0) queue.push(i);
16
    }
17

18
    // 4. BFS拓扑排序
19
    let count = 0;
20
    while (queue.length) {
21
        const current = queue.shift();
22
        count++;
23
        // 遍历当前课程的后继课程
24
        for (const next of graph[current]) {
25
            inDegree[next]--;           // 解除依赖关系
26
            if (inDegree[next] === 0) {  // 若无依赖则加入队列
27
                queue.push(next);
28
            }
29
        }
30
    }
31

32
    // 5. 验证是否遍历所有课程
33
    return count === numCourses;
34
};