图论中的广度优先搜索（BFS）算法 题目描述 广度优先搜索（BFS）是一种用于遍历或搜索图或树结构的算法。它从选定的起始顶点开始，逐层访问所有相邻顶点，再依次访问这些相邻顶点的未访问邻居，确保先访问距离起点最近的顶点。BFS常用于求解无权图的最短路径问题、连通性检测、层级遍历等。 解题过程 初始化 创建一个队列（用于存储待访问的顶点）和一个集合（用于记录已访问的顶点）。 将起始顶点加入队列，并标记为已访问。 遍历队列 当队列非空时，取出队首顶点 u 。 检查 u 的所有未访问邻居顶点： 将邻居标记为已访问，并加入队列。 记录邻居的父节点或距离（例如， 距离[邻居] = 距离[u] + 1 ）。 终止条件 队列为空时，遍历结束。此时所有从起点可达的顶点均被访问。 示例说明 以无权图为例，求顶点 A 到其他顶点的最短路径： 图结构： A 连接 B 和 C ， B 连接 D ， C 连接 D 和 E 。 步骤： 从 A 开始，访问 B 和 C （距离=1）。 访问 B 的邻居 D （距离=2），再访问 C 的邻居 E （距离=2）。 最终得到最短路径： A→B→D （距离2）、 A→C→E （距离2）。 关键点 BFS保证首次访问某顶点时路径最短（无权图中）。 时间复杂度：O(V+E)（V为顶点数，E为边数）。