广度优先搜索(BFS)

定义

广度优先搜索（Breadth First Search）是一种遍历或搜索树与图的策略。它从起点出发一层一层向外扩展，先访问完所有距离为 1 的节点，再访问距离为 2 的节点，依此类推。

原理

BFS 借助队列实现：把起点入队，然后不断从队头取出节点，将其所有未访问的邻居标记并入队，直到队列为空。由于是按距离逐层扩展，在无权图中第一次到达某节点时的路径就是最短路径。同样需要访问标记避免重复处理。

复杂度

• 时间复杂度（邻接表）：O(V+E)
• 空间复杂度（队列）：O(V)

应用场景

• 无权图最短路径
• 层序遍历
• 社交网络的最短关系链
• 状态空间最少步数搜索