跳到主要内容

课程表

问题​

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] 表示想要学习课程 ai，你需要先完成课程 bi。

请你判断是否可能完成所有课程的学习——即判断有向图中是否有环。

示例：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：true

  0 → 1 → 3
  ↓       ↑
  2 ──────┘

学习顺序：0 → 1 → 2 → 3 或 0 → 2 → 1 → 3

来源：LeetCode 207. 课程表

答案​

方法一：BFS 拓扑排序（Kahn 算法，推荐）​

核心思路：

  1. 统计每个节点的入度（有多少先修课）
  2. 将入度为 0 的节点入队（可以直接学的课）
  3. 每次出队一个节点，将其邻居的入度 -1，新的入度为 0 的节点继续入队
  4. 最后检查是否所有节点都被处理过
canFinish.ts
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  // 构建邻接表和入度数组
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);

  for (const [course, pre] of prerequisites) {
    graph[pre].push(course); // pre → course
    inDegree[course]++;
  }

  // 入度为 0 的节点入队
  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  let count = 0; // 已处理的课程数

  while (queue.length > 0) {
    const node = queue.shift()!;
    count++;

    for (const neighbor of graph[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  // 如果所有课程都被处理了，说明没有环
  return count === numCourses;
}

图解：

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

graph: 0→[1,2], 1→[3], 2→[3]
inDegree: [0, 1, 1, 2]

Step 1: 入度 0 的：queue = [0]
Step 2: 出队 0, count=1
  1 入度变 0 → queue = [1]
  2 入度变 0 → queue = [1, 2]
Step 3: 出队 1, count=2
  3 入度变 1 → queue = [2]
Step 4: 出队 2, count=3
  3 入度变 0 → queue = [3]
Step 5: 出队 3, count=4

count=4 === numCourses=4 → 返回 true ✓
复杂度分析
  • 时间复杂度：O(V+E)O(V + E) — V 为课程数，E 为先修关系数
  • 空间复杂度：O(V+E)O(V + E) — 邻接表 + 入度数组

方法二：DFS 检测环​

通过 DFS 检测有向图中是否有环（使用三色标记法）：

canFinishDFS.ts
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  for (const [course, pre] of prerequisites) {
    graph[pre].push(course);
  }

  // 0=未访问, 1=正在访问（在当前路径上）, 2=已完成
  const state = new Array(numCourses).fill(0);

  function hasCycle(node: number): boolean {
    if (state[node] === 1) return true;  // 遇到正在访问的节点 → 有环！
    if (state[node] === 2) return false; // 已经处理过

    state[node] = 1; // 标记为正在访问

    for (const neighbor of graph[node]) {
      if (hasCycle(neighbor)) return true;
    }

    state[node] = 2; // 标记为已完成
    return false;
  }

  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }

  return true;
}
三色标记法
  • 白色（0）：未访问
  • 灰色（1）：正在访问（在当前递归路径上）
  • 黑色（2）：已完成

如果访问到灰色节点，说明存在一条回到当前路径的边 → 有环。

常见面试追问​

Q1: 如何输出一个可行的学习顺序？(LeetCode 210 课程表 II)​

答案：在 BFS 拓扑排序中记录出队顺序：

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);

  for (const [course, pre] of prerequisites) {
    graph[pre].push(course);
    inDegree[course]++;
  }

  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order: number[] = []; // 记录拓扑排序结果

  while (queue.length > 0) {
    const node = queue.shift()!;
    order.push(node);

    for (const neighbor of graph[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return order.length === numCourses ? order : [];
}

Q2: 拓扑排序在前端的应用？​

答案：

  • 构建工具依赖解析：Webpack 解析模块依赖图，确定构建顺序
  • 任务调度：CI/CD 管线中的任务依赖
  • 组件渲染顺序：确保父组件在子组件之前初始化
  • 包管理：npm/pnpm 安装依赖的顺序
// 前端场景：按依赖顺序加载模块
interface Module {
  name: string;
  deps: string[]; // 依赖的模块名
}

function getLoadOrder(modules: Module[]): string[] {
  const graph = new Map<string, string[]>();
  const inDegree = new Map<string, number>();

  for (const m of modules) {
    graph.set(m.name, []);
    inDegree.set(m.name, 0);
  }

  for (const m of modules) {
    for (const dep of m.deps) {
      graph.get(dep)!.push(m.name);
      inDegree.set(m.name, (inDegree.get(m.name) || 0) + 1);
    }
  }

  const queue: string[] = [];
  for (const [name, degree] of inDegree) {
    if (degree === 0) queue.push(name);
  }

  const order: string[] = [];
  while (queue.length > 0) {
    const name = queue.shift()!;
    order.push(name);
    for (const neighbor of graph.get(name)!) {
      const newDegree = inDegree.get(neighbor)! - 1;
      inDegree.set(neighbor, newDegree);
      if (newDegree === 0) queue.push(neighbor);
    }
  }

  return order;
}

Q3: BFS 和 DFS 哪种更好？​

答案：

BFS（Kahn）DFS（三色）
直觉更直观更递归
输出顺序直接就是拓扑序需要后序+翻转
实现难度容易三色标记易出错
推荐面试首选备选方案

相关链接​