图的宽度优先搜索 宽度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图数据结构的算法。它的核心思想是系统地探索一个图，从某个起始顶点开始，优先访问所有与该顶点直接相邻的顶点，然后再去访问这些相邻顶点的相邻顶点，以此类推，像“涟漪”一样逐层向外扩展。 核心思想与直观理解 想象一下你在一个迷宫中，站在起点。BFS的策略是： 首先，你探索从起点出发，一步就能走到的所有房间。 然后，你再探索从这些房间出发，再走一步（也就是从起点算起两步）能到达的所有 新 房间。 接着，探索三步能到达的所有新房间。 这个过程持续下去，直到你访问了所有能到达的房间，或者找到了你的目标。 这种“由近及远”的探索方式确保了从起点到任何被访问顶点的路径都是最短路径（在边没有权重或权重相等的情况下）。 算法实现的关键要素 为了实现BFS，我们需要跟踪几个关键信息： 队列（Queue） ：这是一个“先进先出”（FIFO）的数据结构。它是BFS的核心，用于决定下一个要访问哪个顶点。新发现的顶点被加入到队列的末尾，而从队列前端取出顶点进行访问，这保证了“先被发现的顶点先被访问”，即广度优先。 访问标记（Visited Mark） ：我们需要记录哪些顶点已经被访问过，以避免重复访问和陷入无限循环。通常使用一个布尔数组或集合来实现。 距离/层数信息（Distance/Level） ：在很多应用中，我们关心从起点到各顶点的距离。我们可以用一个数组来记录每个顶点距离起点的边数（即层数）。 算法的详细步骤 假设我们有一个图 G=(V, E) 和一个起点顶点 s。 初始化 ： 创建一个空队列 Q。 创建一个布尔数组 visited[] （大小为 |V|），将所有顶点标记为“未访问”（false）。 （可选）创建一个整数数组 distance[] （大小为 |V|），将所有顶点的距离初始化为一个特殊值（如 -1 或无穷大）。 将起点 s 标记为已访问 ( visited[s] = true )。 将起点 s 的距离设置为 0 ( distance[s] = 0 )。 将起点 s 加入队列 Q。 循环执行以下步骤，直到队列 Q 为空 ： 从队列 Q 的 前端 移出一个顶点，我们称这个顶点为 u 。 检查顶点 u 的所有 未访问过的 邻居顶点 v 。 对于每一个这样的邻居 v ： 将 v 标记为已访问 ( visited[v] = true )。 设置 v 的距离为 u 的距离加 1 ( distance[v] = distance[u] + 1 )。 将 v 加入队列 Q 的 末尾 。 终止 ：当队列为空时，算法结束。此时，所有从起点 s 可达的顶点都已经被访问过了。 算法特性分析 时间复杂度 ：BFS需要检查每个顶点和每条边各一次（对于无向图，每条边会被两个端点各检查一次，但通常仍记为 O(|V| + |E|)）。因此，如果图使用邻接表存储，其时间复杂度为 O(|V| + |E|)。如果使用邻接矩阵，则查找邻居需要 O(|V|) 时间，总时间变为 O(|V|²)。 空间复杂度 ：主要开销来自队列、访问标记和距离数组。队列在最坏情况下（如星形图）可能存储 O(|V|) 个顶点。因此空间复杂度为 O(|V|)。 完备性 ：如果图是连通的，BFS保证能访问到所有顶点。对于非连通图，需要对每个未访问的顶点执行一次BFS才能遍历整个图。 主要应用场景 BFS不仅仅是一个遍历算法，其“由近及远”的特性使其能高效解决多种问题： 无权图的最短路径 ：BFS能天然地找到从起点到所有其他可达顶点的最短路径（以边数计）。 检查图的连通性 ：执行一次BFS后，如果所有顶点都被访问，则图是连通的。 寻找连通分量 ：通过循环对每个未访问的顶点执行BFS，可以找出图的所有连通分量。 网络爬虫 ：搜索引擎的网络爬虫可以看作是以一个网页为起点，通过BFS策略跟随链接遍历整个互联网（或其中一部分）。 社交网络分析 ：计算两个人之间的“度数”或查找特定距离内的朋友。 迷宫求解 ：BFS可以保证找到迷宫出口的最短路径（如果存在）。 图的二分性测试 ：通过BFS过程中交替给顶点“着色”，可以检测一个图是否是二分图。如果在着色过程中发现两个相邻顶点被赋予了相同的颜色，则该图不是二分图。