面试题库 › Java 后端 › 拓扑排序(课程表问题)

拓扑排序(课程表问题)

难度 ★★☆在 11 场真实面经中被问到 方向:Java 后端考点:图论

哪些公司问过

字节跳动2华为2腾讯1快手1拼多多1微软1网易1小马智行1微派1

常见岗位:Java 后端、C/C++ 软件开发、AI 应用 / Agent 开发、推理部署与加速、推荐搜索广告

答案要点

  1. 把依赖关系建模为有向无环图,课程或章节是节点
  2. Kahn 算法:统计入度,入度为 0 入队,出队并给后继入度减一
  3. 结果节点数小于总数说明存在环
  4. DFS 版:后序遍历倒序即拓扑序,用三色标记检测环
  5. 按层 BFS,每轮处理当前所有入度为 0 的节点,所需轮数等于 BFS 层数

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题