拓扑排序(Kahn 与 DFS)与有向无环图
哪些公司问过
答案要点
- 拓扑序要求每条有向边的起点排在终点之前,只有 DAG 存在拓扑序
- Kahn:统计入度,入度为 0 的点入队,出队后把邻点入度减一
- Kahn 判环:输出的节点数小于总节点数即有环
- DFS:后序加入列表再逆序,三色标记中遇到「访问中」节点即有环
- 时间 O(V+E),拓扑序通常不唯一,用小顶堆可得字典序最小的序列
易错点
- DFS 直接用先序顺序当拓扑序
- 只用已访问/未访问两种状态判环,会把交叉边误判为环
- 图中有环时仍把部分序列当结果输出
- 用邻接矩阵存图导致复杂度变成 O(V²)
面试官常见追问
- 和图相关的还了解哪些算法?
- 怎么判断拓扑序是否唯一?
- 无向图怎么判环?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。