面试题库 › C++ / 后端 › BFS 与 DFS 的区别、原理与应用场景

BFS 与 DFS 的区别、原理与应用场景

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

哪些公司问过

网易互娱2大华1字节跳动1拼多多1百度1网易1米哈游1多益网络1阿里高德1

常见岗位:游戏服务端、C/C++ 软件开发、C++ 后端、Go 后端、Java 后端

答案要点

  1. DFS 一条路走到底再回溯,用递归或栈;BFS 按层扩展,用队列
  2. 两者时间复杂度均为 O(V+E)(邻接表),都需要访问标记
  3. BFS 适合无权图最短路径、层序遍历、最少步数问题
  4. DFS 适合回溯枚举、连通分量、环检测、拓扑排序
  5. BFS 宽图时队列占用大,DFS 递归过深可能栈溢出,可改显式栈

易错点

面试官常见追问

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

相关面试题