广度优先搜索BFS
按距离起点的层次扩展相邻顶点。
- 核心约束
- 无权图中首次发现的层数给出最少边数。
- 适用问题
- 无权最短路、层级探索与可达性。
- 边界与取舍
- 前沿较宽时内存开销较大。
时间与空间#
V 为顶点数，E 为边数；使用邻接表，顶点在入队时标记。
- 时间复杂度
- 辅助空间
- ，不含图本身与最终路径输出
队列保存待扩展顶点；无权图或所有边等权时得到按边数计的最短路径。邻接矩阵实现通常 ；从单一起点只扫描可达部分，初始化标记仍可能 。
基础原理参考资料
Princeton · BreadthFirstPaths邻接表上的 BFS 路径搜索及时间、空间界。