图论中的广度优先搜索（BFS）算法 题目描述 广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图（或树）的算法。它从某个起始顶点开始，逐层访问所有相邻顶点，再访问相邻顶点的相邻顶点，以此类推。BFS 常用于求解无权图的最短路径问题、连通性检测等。题目要求：给定一个无向图（或有权图但仅需路径长度计数）和起始顶点，使用 BFS 找出从起始顶点到所有其他顶点的最短路径（以边数计算）。 解题过程 核心思想 BFS 通过队列（FIFO 结构）实现层级扩展。从起点开始，先访问所有直接相邻的顶点（第一层），再访问这些相邻顶点的未访问过的相邻顶点（第二层），确保每次扩展的路径是最短步数。 算法步骤 初始化 ： 创建一个队列，将起始顶点入队。 创建一个距离数组 dist[] ，初始化所有顶点距离为无穷大（或 -1）， dist[起点] = 0 。 创建一个访问标记数组 visited[] ，标记起点已访问。 循环处理队列 ： 当队列非空时，取出队首顶点 u 。 遍历 u 的所有未访问过的相邻顶点 v ： 标记 v 为已访问。 设置 dist[v] = dist[u] + 1 （表示从起点到 v 的最短距离）。 将 v 入队。 结束条件 ：队列为空时，说明所有从起点可达的顶点均已访问。 示例演示 假设无向图顶点为 {0,1,2,3}，边为 (0,1), (0,2), (1,2), (2,3)，起点为 0。 初始：队列 = [ 0]， dist[0]=0 ，其他为 -1。 处理顶点 0： 访问邻居 1 和 2： dist[1]=1 ， dist[2]=1 ，队列变为 [ 1,2 ]。 处理顶点 1： 邻居 0（已访问）和 2（已访问），无新顶点入队，队列变为 [ 2 ]。 处理顶点 2： 邻居 0、1（已访问）和未访问的 3： dist[3]=2 ，队列变为 [ 3 ]。 处理顶点 3：无未访问邻居，队列空。 结果： dist[] = [0,1,1,2] 。 关键点 BFS 保证第一次到达顶点时的路径一定是最短路径（无权图中）。 时间复杂度 O(V+E)（V 为顶点数，E 为边数），空间复杂度 O(V)。 应用扩展 若图有权重，BFS 仅适用于边权均相同的情况（可视为无权图）。 可通过记录路径父节点回溯具体最短路径。