如何判断图中是否存在环?有向图和无向图有何不同?
哪些公司问过
答案要点
- 有向图 DFS 三色标记:遇到指向灰色(在递归栈中)节点的边即有环
- 有向图拓扑排序:能输出的节点数少于总数则有环
- 无向图 DFS:遇到已访问且非父节点的邻居即有环
- 无向图并查集:加边时两端已在同一集合即成环
- 复杂度 O(V+E);链表判环用快慢指针
易错点
- 有向图只用访问过标记,把交叉边误判为环
- 无向图 DFS 没有排除父节点
- 递归 DFS 在大图上栈溢出,需要改迭代
面试官常见追问
- 为什么无向图不能直接用有向图的三色法或拓扑排序?
- 如何找出环上的具体节点?
- 实际工程里哪里会用到有向图判环?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。