拓扑排序：课程表问题

拓扑排序：课程表问题

一、面试常考点

1. 使用前提

有向无环图（DAG）。（深入阅读：课程表建图与判环）

2. Kahn 算法

入度为 0 入队，出队后削减邻接点入度。（深入阅读：Kahn 算法实现）

二、示例代码

function canFinish(numCourses, prerequisites) {
  const g = Array.from({ length: numCourses }, () => [])
  const indeg = Array(numCourses).fill(0)

  for (const [a, b] of prerequisites) {
    g[b].push(a)
    indeg[a]++
  }

  const q = []
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i)

  let visited = 0
  while (q.length) {
    const u = q.shift()
    visited++
    for (const v of g[u]) if (--indeg[v] === 0) q.push(v)
  }

  return visited === numCourses
}