图的广度优先搜索
图的广度优先搜索（BFS）从起始顶点出发，优先访问当前节点的所有相邻顶点，再逐层向外扩展遍历，依靠队列实现，适合求最短路径、寻找连通分量，按层遍历各个结点。
与深度优先搜索（DFS）“不撞南墙不回头”的策略不同，图的广度优先搜索（Breadth-First Search，简称 BFS） 的核心思想是 “层层推进、由近及远”：从起始顶点出发，优先访问离起始节点最近的所有邻居节点，然后再依次访问这些邻居节点的邻居。这种逐层向外扩张的特性，使其非常适合用于求解无权图的最短路径问题。
广度优先搜索（BFS）的核心是通过 队列（FIFO） 与 已访问标记 来驱动一个简单的重复循环：
- 起点入队：从源节点开始，将其标记为已访问并压入队列。
- 出队处理：取出队列头部的节点进行访问/处理。
- 邻居入队：检查该节点的所有邻居——对于尚未访问的邻居，立即标记为已访问并压入队列末尾。
- 循环终止：重复步骤 2 和 3，直到队列为空，遍历结束。
以下是以邻接表存储图的 BFS 经典实现：
#include <iostream>#include <vector>#include <queue>
using namespace std;
// BFS 遍历函数void bfs(int start, const vector<vector<int>>& adj, int numVertices) { vector<bool> visited(numVertices, false); queue<int> q;
// 起始节点初始化 visited[start] = true; q.push(start);
cout << "BFS 遍历顺序: ";
while (!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; // 处理当前节点
// 遍历所有邻接节点 for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; // 入队时即标记已访问 q.push(v); } } } cout << endl;}
int main() { int numVertices = 6; vector<vector<int>> adj(numVertices);
// 构建有向图 adj[0] = {1, 2}; adj[1] = {3, 4}; adj[2] = {5}; adj[3] = {}; adj[4] = {5}; adj[5] = {};
bfs(0, adj, numVertices); // 输出: 0 1 2 3 4 5
return 0;}| 复杂度 | 邻接表表示 | 邻接矩阵表示 | 说明 |
|---|---|---|---|
| 时间复杂度 | 为顶点数， 为边数。每个顶点入队/出队一次，每条边被检查一次。 | ||
| 空间复杂度 | 需要辅助队列存储节点，最坏情况下队列中可能包含 个节点。 |
| 维度 | 广度优先搜索（BFS） | 深度优先搜索（DFS） |
|---|---|---|
| 数据结构 | 队列（Queue） | 栈（Stack / 递归） |
| 遍历路径 | 按层次由近及远辐射扩散 | 沿单条路径纵向深挖到底后回溯 |
| 最短路径 | 能直接求出无权图的最短路径 | 无法保证找到最短路径 |
| 应用场景 | 寻找最短路径、社交网络六度分割、广播传播 | 寻找路径、拓扑排序、连通分量、迷宫回溯 |
- 无权图的最短路径问题：求从起点到终点的最少边数（如社交网络中的“共同好友”或“最短关系链”）。
- 层次遍历：树的层序遍历（如二叉树的层序输出、按层打印网络拓扑）。
- 连通分量计算：寻找无向图中相连的组件（如 Flood Fill 图像填充算法）。