拓扑排序(课程表问题)
哪些公司问过
答案要点
- 把依赖关系建模为有向无环图,课程或章节是节点
- Kahn 算法:统计入度,入度为 0 入队,出队并给后继入度减一
- 结果节点数小于总数说明存在环
- DFS 版:后序遍历倒序即拓扑序,用三色标记检测环
- 按层 BFS,每轮处理当前所有入度为 0 的节点,所需轮数等于 BFS 层数
易错点
- 忘了检测环,直接输出结果
- 入度统计错误,重复边没有处理
- 用邻接矩阵导致复杂度偏高
- 把拓扑序当作唯一的
面试官常见追问
- DFS 怎么检测环?
- 怎么得到字典序最小的拓扑序?
- 怎么判断拓扑序是不是唯一的?
- 拓扑排序有哪些应用?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。