课程表问题

题目如何转成图模型？

• 顶点: 每门课程, 用 0 到 numCourses - 1 的编号表示;
• 有向边: 先修关系 [a, b] 表示学 a 之前必须先学 b, 即存在边 b → a;
• 问题: 判断这张有向图是不是 DAG, 或输出一个合法的学习顺序;

如何判断能否修完全部课程？

• 做法: 建图后跑拓扑排序, 结果非空且长度等于课程数才能修完;
• 环的含义: 存在环说明课程之间互相依赖, 无法排课;

const canFinish = function (numCourses, prerequisites) {
  const graph = new Map(Array.from({ length: numCourses }, (_, i) => [i, []]));
  for (const [a, b] of prerequisites) graph.get(b).push(a);
  const order = topologicalSort(graph);
  return order != null && order.length === numCourses;
};

• 复用: topologicalSort 的定义见 拓扑排序;

如何输出一个合法的学习顺序？

• 差异: 直接把拓扑序列作为答案返回;
• 环的返回: 存在环时按题目要求返回空数组;

const findOrder = function (numCourses, prerequisites) {
  const graph = new Map(Array.from({ length: numCourses }, (_, i) => [i, []]));
  for (const [a, b] of prerequisites) graph.get(b).push(a);
  const order = topologicalSort(graph);
  return order != null && order.length === numCourses ? order : [];
};

复杂度如何？

• 时间: O(V + E), V 为课程数, E 为先修关系数;
• 空间: O(V + E), 邻接表与入度表;