DFS 是「一条路走到黑」，BFS 是水波纹：从起点出发，先通知直接相连的节点（第 1 圈），再由它们通知下一圈，一圈一圈、不越层。工具是队列（排队：先进先出）。水波一层层扩，所以节点第一次被到达，一定是最短路径（无权图：层数 = 最短步数）。
BFS = 往池塘扔石子，看波纹怎么扩散：石子落点（起点）先激起第 1 圈波纹——直接挨着起点的节点（第 1 层）；这些节点又把波纹传给第 2 圈——挨着第 1 层的新节点（第 2 层）；一圈一圈向外，永远先扩完这一圈，才轮到下一圈，绝不越层。记录「当前波纹前沿」的工具是队列——排队打饭：先进先出，先来先服务。算法：起点入队 → 每次取出队头一个节点，把它所有没访问过的邻居入队（它们就是下一圈）→ 直到队空。对比 DFS：DFS「一条路走到黑」靠递归/栈回头，BFS「一层层推进」靠队列排队。因为波纹按层扩，一个节点被第一次到达时，走的路一定最短（无权图里层数 = dist = 最短步数）——这是 BFS 最值钱的性质。
// DFS：一条路走到黑，靠递归（栈）回头 // BFS：一层层推进，靠队列排队（先进先出，像排队打饭：先来先服务） // // BFS 骨架（无权无向图，邻接表）： // 1. 起点 s 入队，vis[s] = true（入队即标记） // 2. while 队列非空： // u = 取队头（并出队） // 对 u 的每个邻居 v：若没访问过 → vis[v] = true，v 入队 // 3. 队空 = 所有能走到的节点都访问完了 // // 关键细节：vis 在「入队那一刻」标，不是出队时才标 // 否则同一个 v 可能从两个邻居分别入队两次（重复排队，白干）
// 图：边 1-2、1-3、2-4、3-4、4-5、5-6；起点 s = 1 // // 队列状态推进（每次：取队头 → 它的未访问邻居入队并标 vis）： // 初始：q = [1]，vis[1] = 1，dist[1] = 0 // 取 1：邻居 2、3 未访问 → 入队并标，dist = 1 q = [2, 3] // 取 2：邻居 1（已访问）、4（未访问 → 入队，dist = 2） q = [3, 4] // 取 3：邻居 1（已访问）、4（已访问，入队时就标了）→ 无新人 q = [4] // 取 4：邻居 2、3（已访问）、5（未访问 → 入队，dist = 3） q = [5] // 取 5：邻居 4（已访问）、6（未访问 → 入队，dist = 4） q = [6] // 取 6：邻居 5（已访问）→ 无新人 q = [] 队空，结束！ // // 分层结果：第 0 层 {1}；第 1 层 {2, 3}；第 2 层 {4}；第 3 层 {5}；第 4 层 {6} // dist：1→0，2→1，3→1，4→2，5→3，6→4
// 为什么 BFS 第一次到达 = 最短？（层不越界原则） // 第 k 层的全部节点，一定在第 k+1 层任何节点入队之前处理完 // （队列排队：先进先出，当前圈排完才轮到下一圈） // → 节点 v 若在第 k 层被发现，就不可能还有更短的路（否则它该在第 < k 层被发现） // // 反例：DFS 的第一到达可能不是最短 // 图：边 1-2、2-3、3-4、1-4（1 直接连着 4！） // DFS(1)：1 → 2 → 3 → 4（顺序 1 2 3 4）——第一次到 4 走了 3 条边 // 但最短是 1 → 4 直接 1 条边！DFS「一头扎到底」错过了捷径 // BFS(1)：第 1 层 {2, 4}——4 直接被发现，dist[4] = 1 ✓ // // 前提：无权图（每条边都算 1 步）。边有权重（高速 1 步 / 山路 10 步）→ BFS 不管用
// 6 节点图（边 1-2、1-3、2-4、3-4、4-5、5-6），起点集合 {1, 6}（两个「水源地」） // // 初始化：dist[1] = 0、dist[6] = 0，q = [1, 6]（一起入队！） // 取 1：邻居 2、3 → 入队，dist = 1 q = [6, 2, 3] // 取 6：邻居 5 → 入队，dist = 1 q = [2, 3, 5] // 取 2：邻居 4 → 入队，dist = 2 q = [3, 5, 4] // 取 3：邻居 4（已标记）→ 无新人 q = [5, 4] // 取 5：邻居 4（已标记）、6（已访问）→ 无 q = [4] // 取 4：邻居 2、3、5（全已访问）→ 队空，结束 // // dist：1→0，6→0，2→1，3→1，5→1，4→2 // 含义：每个节点「离最近水源」的步数 // 应用：最近的消防栓 / 最近的充电桩 / 多个基地同时派援兵 // （两个波纹同时扩，先碰到某点的波 = 最近的水源）
// 题目：读入 n 节点 m 边的无权无向图和起点 s，输出 s 到每个节点 1..n 的最短距离（边数），不可达输出 -1。 // 输入：第 1 行 n m；接下来 m 行每行 u v（无向边）；最后 1 行 s。 #include <iostream> #include <queue> #include <vector> using namespace std; const int N = 100005; vector<int> adj[N]; int dist[N]; // dist[i] = s 到 i 的最短步数；-1 = 还没到达（兼当 vis） int n, m; int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int s; cin >> s; for (int i = 1; i <= n; i++) dist[i] = -1; // -1 当 vis 用：没到达过 queue<int> q; dist[s] = 0; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < (int)adj[u].size(); i++) { int v = adj[u][i]; if (dist[v] == -1) { // 第一次到达 = 最短，立即标记 dist[v] = dist[u] + 1; q.push(v); } } } for (int i = 1; i <= n; i++) { cout << dist[i]; if (i < n) cout << " "; } cout << endl; return 0; } // 样例：n=6, m=6；边：1 2 / 1 3 / 2 4 / 3 4 / 4 5 / 5 6；s = 1 // 输出：0 1 1 2 3 4 //（dist = BFS 层数：1→0，2→1，3→1，4→2，5→3，6→4）