BFS

定义

BFS（Breadth First Search，广度优先搜索）是一种图的遍历算法，从起始顶点出发，逐层访问所有邻接顶点，先访问距离近的顶点。

算法思想

1. 访问起始顶点，标记为已访问，入队
2. 队首顶点出队，访问其所有未访问的邻接顶点，标记并入队
3. 重复步骤 2，直到队列为空

实现

通常使用队列实现。

时间复杂度

• 邻接矩阵：$O(V^2)$
• 邻接表：$O(V+E)$

应用

• 最短路径（无权图）
• 连通分量检测
• 层次遍历
• 最小生成树（Prim 算法的辅助）