面试题库 › Java 后端 › 手写 BFS 广度优先搜索

手写 BFS 广度优先搜索

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

哪些公司问过

腾讯1滴滴1

常见岗位:C++ 后端

答案要点

  1. 用队列保存待访问节点,起点先入队并标记
  2. 出队后遍历邻居,未访问的邻居先标记再入队,防止重复入队
  3. 按层处理:记录每层队列长度,或用 dist 数组记录距离
  4. 无权图中 BFS 首次到达即最短路径
  5. 复杂度:邻接表 O(V+E),邻接矩阵 O(V²);不连通图需对每个连通分量分别 BFS

易错点

面试官常见追问

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

相关面试题