跳到主要内容

有向依赖与拓扑排序

本节目标

用入度与队列处理先后依赖，判断有向图是否有环并构造可行顺序。

课程、任务和构建步骤都可抽象为有向图。一条边 A → B 表示“完成 A 后才可做 B”：A 是前置条件，B 是依赖它的任务。拓扑排序要找的是一个顶点序列，使每条边的起点都排在终点之前；只有无环有向图才存在这样的序列。

识别信号​

  • 题目出现“先修”“依赖”“先完成”“安装顺序”或“任务编排”；
  • 一条关系 [a, b] 的语义是“做 a 前要先做 b”；
  • 需要判断能否全部完成，或输出任意一个合法顺序；
  • 关系是有方向的，A → B 与 B → A 不是同一件事。

问题模型与核心不变量​

把 [course, prerequisite] 翻译为 prerequisite → course，并让 course 的入度加一。入度表示“这个任务还欠多少尚未完成的前置条件”。

Kahn 算法维护一个队列：其中永远只放当前入度为 0 的任务。弹出一个任务等价于完成它；沿其出边把后继任务的入度减一。某个后继第一次降到 0，说明它的所有前置条件都已完成，才能入队。这个不变量保证输出顺序的每一步都合法。

若队列提前空了但仍有顶点未处理，余下顶点都至少有一条来自余下集合的入边；沿入边不断追溯必会形成环。因此“处理数是否等于顶点数”恰好判定能否完成全部任务。

通用模板​

graph = n 个空邻接表，indegree = n 个 0
for [course, before] in prerequisites:
    graph[before].append(course)
    indegree[course] += 1

把所有 indegree == 0 的顶点入队
while 队列非空:
    u = 出队
    记录 u 为已处理
    for v in graph[u]:
        indegree[v] -= 1
        若 indegree[v] == 0: v 入队

若 processed == n：无环；否则：存在环

邻接表保存“完成当前任务会解锁谁”，入度保存“谁仍未被解锁”。不要把边反过来：反向后，减入度的对象也会错，样例偶尔看似可过却无法保持上述不变量。

模板变体​

  • 可行性：只计数，最后返回 processed == n，对应课程表。
  • 构造顺序：每次出队时把顶点写入 order；仅当 order 长度为 n 才返回它，否则返回空序列。
  • 字典序最小顺序：把 FIFO 队列换成最小堆；这是额外要求，普通题不需要为此增加复杂度。
  • DFS 三色法：用“未访问、访问中、已完成”识别回边，也能拓扑排序；本栏优先掌握入度模板，因为“可开始的任务”与题意直接对应。

母题序列​

按必学顺序练习：

  1. 课程表（必学）：只需确认 Kahn 过程是否能处理全部课程。
  2. 课程表 II（必学）：在同一过程里记录出队顺序，并在有环时拒绝输出不完整答案。

常见误区​

  • 将 [a, b] 写成 a → b，把依赖关系完全翻转。
  • 初始化时只入队一个入度为 0 的顶点，遗漏独立任务或其他连通分量。
  • 见到一个入度为 0 的点就认为全图无环；必须比较最终处理数。
  • 认为拓扑序唯一。多个可用顶点并存时，不同出队顺序都可以合法。
  • 有环时直接返回已收集的前缀；构造题必须返回空序列。

迁移方向​

当节点代表模块、文件、菜谱、项目任务或事件时，先把自然语言统一成“前置条件 → 依赖者”，再套入度模板。若题目还要求每项的最早完成时间或关键路径，需要在拓扑序上做 DP；若边没有方向，应转到连通性模型，而不是强行套拓扑排序。