广度优先搜索
入门BFS 用队列按层推进，天然求解无权最短路。
// 算法讲解
广度优先搜索
输入节点数、起点和边列表，观察 BFS 按层扩展的过程。
待机
速度 中
待机 ⌨1vector<int> bfs(int start, vector<vector<int>>& adj) {
2 int n = adj.size();
3 vector<int> dist(n, -1);
4 queue<int> q;
5 dist[start] = 0;
6 q.push(start);
7 while (!q.empty()) {
8 int u = q.front(); q.pop();
9 for (int v : adj[u]) {
10 if (dist[v] == -1) {
11 dist[v] = dist[u] + 1;
12 q.push(v);
13 }
14 }
15 }
16 return dist;
17}
复杂度分析
时间 O(V + E)
空间 O(V)
最优 O(1) 起点即目标
最坏 O(V + E)
算法讲解
广度优先搜索从起点出发，先访问所有距离为 1 的节点，再访问距离为 2 的节点，依此类推。
因为队列保证了"先发现的先处理"，所以第一次到达某个节点时走的路径一定是最短的。
它在无权图的最短路径、层级遍历和连通分量检测中是最基础的工具。
实现时需要 visited 数组防止重复访问，队列用于维护"待处理"的节点序列。