如何判断拓扑排序结果是否唯一？
简化版
判断拓扑序是否唯一，可以在 Kahn 算法过程中观察队列。
如果每一步入度为 0 的节点都只有一个，那么选择没有分歧，拓扑序唯一；如果某一步同时有多个入度为 0 的节点，就至少存在不同选择，拓扑序不唯一。
前提是图必须是 DAG。如果存在环，则根本没有拓扑序。
详细版
Kahn 拓扑排序流程：
- 统计所有节点入度；
- 把入度为
0的节点入队； - 每次弹出一个节点，删除它的出边；
- 新入度变成
0的节点入队。
唯一性判断：
while queue not empty:
if queue.size > 1:
not unique
pop one| 队列大小 | 含义 |
|---|---|
0 且未处理完 | 有环 |
1 | 当前选择唯一 |
> 1 | 存在多个可选节点，拓扑序不唯一 |
完整版教学
1. 拓扑排序为什么可能不唯一
DAG 中如果两个节点之间没有依赖关系，它们的先后顺序可能都合法。
例如：
A -> C
B -> CA, B, C 和 B, A, C 都是合法拓扑序。
所以拓扑排序常常不是唯一答案。
2. Kahn 算法里的选择分歧
Kahn 算法每一步选择一个入度为 0 的节点。
入度为 0 表示当前没有前置依赖，可以被安排。
如果某一刻队列里有多个这样的节点，就说明它们之间没有当前必须遵守的先后约束，因此可以交换顺序。
拓扑序唯一性的关键观察点就是：每一步是否只有一个可选节点。
3. 为什么队列大小大于 1 就不唯一
假设某一步队列里有 x 和 y 两个入度为 0 的节点。
选择 x 再选择 y 合法；选择 y 再选择 x 也合法。
由于它们当前都没有未满足依赖，交换它们不会违反已经处理的约束。
因此只要出现一次队列大小大于 1，拓扑序就不唯一。
4. 为什么每一步都只有 1 个就唯一
如果每一步只有一个入度为 0 的节点，算法没有任何选择空间。
下一位必须是它。
从第一位到最后一位都被强制确定，所以拓扑序唯一。
这其实是一个逐步归纳：第 k 个位置没有分歧，则整个序列没有分歧。
5. 环要先排除
如果图有环，就不存在拓扑排序。
Kahn 算法中表现为：
processedCount < V也就是队列空了，但还有节点没有处理。
| 情况 | 结论 |
|---|---|
| 处理节点数小于 V | 有环，无拓扑序 |
| 全部处理且出现多选 | 有拓扑序但不唯一 |
| 全部处理且每步单选 | 拓扑序唯一 |
6. DFS 拓扑排序能判断唯一吗
DFS 也能生成拓扑序，但判断唯一性不如 Kahn 直观。
更常见做法是：
- 先用任意方法得到一个拓扑序；
- 检查序列相邻节点之间是否都有边约束；
- 如果每对相邻都有直接依赖，通常可以说明序列被锁定。
但面试中最推荐 Kahn 队列大小判断，简单清楚。
7. 典型应用场景
拓扑序唯一性常用于：
| 场景 | 问题 |
|---|---|
| 课程安排 | 学习顺序是否唯一 |
| 构建系统 | 任务执行顺序是否有多种 |
| 序列重建 | 给定子序列能否唯一还原原序列 |
| 依赖分析 | 约束是否足够强 |
序列重建类题目尤其常考这个判断。
8. 常见误区与追问
- 误区：拓扑排序算法输出一个结果，就说明唯一。 算法只是选了一个合法结果，不代表没有其他结果。
- 误区：队列初始大小为 1 就够。 要检查每一步，而不是只检查初始状态。
- 误区：有环时拓扑序不唯一。 有环时是不存在拓扑序，不是“不唯一”。
- 追问：为什么队列大于 1 就能交换？ 因为这些节点当前都没有未满足前置依赖，选择顺序有分歧。
- 追问：用 DFS 怎么判断？ 可以辅助检查相邻拓扑序是否被边约束，但 Kahn 更直接。