面试题库 › C++ / 后端 › 如何判断图中是否存在环?有向图和无向图有何不同?

如何判断图中是否存在环?有向图和无向图有何不同?

难度 ★★☆在 3 场真实面经中被问到 方向:C++ / 后端考点:图论

哪些公司问过

美团1字节跳动1拼多多1

常见岗位:后端开发、Web 前端

答案要点

  1. 有向图 DFS 三色标记:遇到指向灰色(在递归栈中)节点的边即有环
  2. 有向图拓扑排序:能输出的节点数少于总数则有环
  3. 无向图 DFS:遇到已访问且非父节点的邻居即有环
  4. 无向图并查集:加边时两端已在同一集合即成环
  5. 复杂度 O(V+E);链表判环用快慢指针

易错点

面试官常见追问

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

相关面试题