手写 BFS 广度优先搜索
哪些公司问过
答案要点
- 用队列保存待访问节点,起点先入队并标记
- 出队后遍历邻居,未访问的邻居先标记再入队,防止重复入队
- 按层处理:记录每层队列长度,或用 dist 数组记录距离
- 无权图中 BFS 首次到达即最短路径
- 复杂度:邻接表 O(V+E),邻接矩阵 O(V²);不连通图需对每个连通分量分别 BFS
易错点
- 出队时才标记已访问,导致节点被重复入队
- 网格题忘记检查越界或障碍
- 需要分层时没有固定当前层的大小,层数统计错误
面试官常见追问
- BFS 和 DFS 怎么选?
- 如果边有权重还能用 BFS 吗?
- 如何输出最短路径本身?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。