课程表:根据任务依赖判断能否全部完成
哪些公司问过
答案要点
- 建模为有向图,依赖 B 先于 A 对应边 B 指向 A
- 能全部完成等价于图中无环
- Kahn 算法:入度为 0 入队,出队计数,计数等于节点数则无环
- DFS 三色标记,遇到访问中的节点即有环
- 时间空间均为 O(V + E);输出顺序记录出队序列,最少轮数按层 BFS
易错点
- 边方向建反,导致拓扑序反了
- DFS 只用一个 visited 标记,把汇合误判为环
- 任务数很大时递归 DFS 栈溢出,需要改为迭代或用 BFS
面试官常见追问
- 要求输出一种可行的完成顺序怎么改?
- 如果每轮可以并行完成所有就绪任务,最少几轮?
- DFS 判环为什么要三种状态而不是两种?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。