🕳️
深度优先搜索 DFS
一条路走到底，走不通就回头——走迷宫的标准姿势
💡 打个比方
把一张地铁线路图想成一张地图：站点叫顶点（vertex），线路叫边（edge）。深度优先搜索（DFS，Depth-First Search）就是走迷宫的姿势：认准一条路一直走到底，走到死胡同就退回来，再换一条没走过的路。为了防止在同两个站点之间来回打转，手里拿一本到访本（visited 数组）：到过的站就画钩，绝不二次进。
DFS 不保证找到"最近的路"，但它能保证把这个连通块里所有能到的站一个不漏全走到——所以"能不能到？""这块有几块？"这类问题都归它管。
图（graph）：一堆顶点 + 一堆边，记作 G=(V, E)。每个顶点旁边记一张"邻居清单"叫邻接表（adjacency list）。DFS：从某顶点出发，每次挑一个没访问过的邻居走过去并递归深入；邻居都访问完就回溯；visited 数组防回头路。
🖼️ 大图看明白
左边是今天的"演练场"：一张 7 个顶点、6 条边的图（7 号是座孤岛）。橙色粗线是 DFS 实际走过的路线，橙色数字是到达顺序——注意 5 和 3 的位置：DFS 是走到 6 才拐去 5、再拐去 3 的，"走到底"不是"按编号走"。
🧩 子任务 1：图的词汇表——顶点、边、邻接表
🎯 小目标：会读图、会写邻接表（每个顶点的"邻居清单"）
图（graph）= 一堆顶点 + 一堆边。地铁图就是图：站点是顶点，线路是边。一条边两端能双向走的图叫无向图（undirected）；只能单向走的叫有向图（digraph，带箭头的）。今天的演练场是无向图。
代码里怎么存图？最常用的是邻接表（adjacency list）：一个顶点配一张"邻居清单"。上面这张图的邻接表是：
// 无向图：每条边要在两个顶点的清单里各记一次（对称）
顶点 1: 2 3
顶点 2: 1 4
顶点 3: 1 5
顶点 4: 2 6
顶点 5: 3 6
顶点 6: 4 5
顶点 7: （空，孤岛）
考点：邻接表是无向图时对称的——1 的清单里有 2，2 的清单里必有 1。n 个顶点 m 条边，邻接表总长度 = 2m。
✅ 小检查：顶点 4 有几个邻居？如果新修一条"7 号站到 2 号站"的线路，邻接表要改几处？
看看答案
4 的邻居是 2 和 6，共 2 个。新线路要改 2 处：2 的清单加 7，7 的清单加 2（无向边两边都要记）。
🧩 子任务 2：DFS 怎么走？（手推到达顺序）
🎯 小目标：能一步步手推 DFS 顺序，说清 visited 为什么必不可少
规则只有三条：① 到站先打卡（vis[u]=1）；② 挑一个没打过卡的邻居，走过去（递归）；③ 邻居都打过卡了，就退回来（回溯）。按图中邻接表的顺序推一遍：
- 到 1（起点，打卡）。邻居 2、3 都没卡 → 去 2。
- 到 2，打卡。邻居 1（已卡）、4 → 去 4。
- 到 4，打卡。邻居 2（已卡）、6 → 去 6。
- 到 6，打卡。邻居 4（已卡）、5 → 去 5。
- 到 5，打卡。邻居 3（没卡！）、6（已卡）→ 去 3。
- 到 3，打卡。邻居 1、5 都已卡 → 死路，一层层退回到 1。
- 回到 1，邻居 2、3 全卡过 → 第一轮结束。到达顺序：1 2 4 6 5 3。
注意 7 号孤岛根本没被走到——DFS 一轮只能覆盖一个连通块。所以外层要循环：发现还有没打卡的顶点，就从它新开一轮。开几轮 = 几个连通块。
为什么必须 visited：无向图里 2 和 4 互连。如果不打卡，DFS 会 2→4→2→4→2……在两个点之间永远来回打转，程序直接卡死。打卡本是 DFS 的"安全带"。
✅ 小检查：把 1 号顶点的邻居顺序改成 [3, 2]（其余不变），DFS 从 1 出发后第一个到的是谁？完整到达顺序是什么？
看看答案
第一个到 3。顺序：1 → 3 → 5（3 的未访问邻居）→ 6（5 的未访问邻居）→ 4（6 的未访问邻居）→ 2（4 的未访问邻居）→ 2 的邻居 1、4 都已卡，退回。完整顺序：1 3 5 6 4 2。邻居顺序一变，DFS 顺序跟着变——DFS 的顺序不是唯一的。
🧩 子任务 3：DFS 递归代码（回溯 = 函数返回）
🎯 小目标：看懂递归 DFS，说清"回溯"在代码里对应什么
上面手推的三步规则，写成 C++ 只有四行核心：
// g 是邻接表，vis 是打卡本
void dfs(int u) {
vis[u] = 1; // 到站，打卡
for (int v : g[u]) {
if (!vis[v]) dfs(v); // 没卡的邻居 → 递归深入
}
// 走到这里 = u 的邻居全卡完 = 回溯（函数 return，退回上一层）
}
"回溯"听起来神秘，其实就是函数 return：dfs(4) 里的 for 循环跑完，dfs(4) 返回，控制权交回 dfs(2)——就像人从 4 号站走回 2 号站再选下一条路。调用栈（谁调用了谁）就是你来时的路线。
考点：DFS 递归三要素——打卡（vis[u]=1，先于递归）、枚举邻居、只往没访问的走。漏掉 vis 检查 = 死循环。
✅ 小检查：程序运行到"正在执行 dfs(4) 的 for 循环"这一刻，调用栈里有哪几帧？
看看答案
main → dfs(1) → dfs(2) → dfs(4)，共 4 帧（含 main）。栈顶是 dfs(4)；它返回后栈顶变回 dfs(2)，继续 2 的下一个邻居。
🧩 子任务 4：DFS 的两大应用——连通块计数 & 找通路
🎯 小目标：会用"外层循环 + DFS"数连通块，说清 DFS 找路的能力与局限
数连通块：外层 for 扫所有顶点，发现没打卡的，就从它新开一轮 DFS 并 comp++。开几轮就是几个连通块。演练场：第一轮从 1 出发，把 1 2 3 4 5 6 全卡掉；轮到 7 发现没卡 → 第二轮 → comp = 2。
找通路：DFS 能回答"1 号站能不能到 5 号站？"（能——5 被卡到了），还能输出走法：每次递归时记下"我是从谁这里来的"（父亲数组），到终点后顺着父亲倒着拼，就是完整路线：1 → 2 → 4 → 6 → 5。
局限：DFS 找到的路不一定是最近的——1→5 它给出 4 条边的绕路，而最近的路 1→3→5 只有 2 条边。"能不能到 / 有哪些点能到"找 DFS；"最少几步到"找 BFS（下一课）。
✅ 小检查：① 从 1 出发能到 7 吗？② 新修一条 5—7 线路后，连通块还剩几个？
看看答案
① 不能：7 是孤岛，第一轮 DFS 根本走不到它。② 1 个：5—7 这条新边把孤岛接进大图，全图连通，外层循环只开一轮。
💻 完整代码
建图 → 外层循环开新轮 → DFS 打卡走到底。输出连通块数和到达顺序。
// 图 DFS：连通块计数 + 到达顺序
#include <bits/stdc++.h>
using namespace std;
int n, comp = 0;
vector<vector<int>> g; // 邻接表
vector<int> vis, order; // 打卡本 + 到达顺序
void dfs(int u) {
vis[u] = 1; // 到站，先打卡
order.push_back(u); // 记下到达顺序
for (int v : g[u]) {
if (!vis[v]) dfs(v); // 没卡的邻居 → 递归深入
}
// 函数返回 = 回溯
}
int main() {
n = 7;
g.assign(n + 1, {});
auto add = [&](int a, int b) { g[a].push_back(b); g[b].push_back(a); };
add(1, 2); add(1, 3); add(2, 4); add(3, 5); add(4, 6); add(5, 6);
// 顶点 7 是孤岛，没有边
for (int i = 1; i <= n; i++) {
if (!vis[i]) { comp++; dfs(i); } // 每个未访问顶点开一轮
}
printf("连通块数: %d\n", comp); // 输出：2
printf("DFS 顺序: ");
for (int x : order) printf("%d ", x);
printf("\n"); // 输出：1 2 4 6 5 3 7
return 0;
}
易错点：① 外层"每个未访问顶点开新轮"不能省，否则漏掉孤岛等连通块。② vis[u]=1 必须在递归之前：放 for 循环之后的话，2→4→2→4 会无限互访（无向图没有"来路"概念，全靠打卡挡）。③ 题目要求"按编号从小到大访问邻居"时，邻接表要排好序再 push。
✋ 你来试试
第 1 题：写出演练场图中顶点 1~6 的邻接表，并验证"总条目数 = 2 × 边数"。
1: 2 3；2: 1 4；3: 1 5；4: 2 6；5: 3 6；6: 4 5。总条目 12 = 2 × 6 条边 ✓（无向边两边各记一次）。
第 2 题：DFS 起点改成 5（邻接表不变），完整到达顺序是什么？
5 3 1 2 4 6。推法：5 的邻居 3、6 → 先去 3；3 的未访问邻居 1 → 去 1；1 的未访问邻居 2 → 去 2；2 的未访问邻居 4 → 去 4；4 的未访问邻居 6 → 去 6；6 的邻居 4、5 都已卡，退回。起点换一换，顺序大变。
第 3 题：图有 100000 个顶点、200000 条边（很"稀疏"），为什么存图要用邻接表而不是 n×n 的二维数组（邻接矩阵）？
邻接矩阵要 n×n = 100000 × 100000 = 100 亿个格子，绝大多数是 0，空间爆炸；邻接表只存真实存在的边：2m = 400000 条记录，省得多。稀疏图（边远少于顶点数的平方）一律邻接表。
🎯 一句话记住：DFS = 走到底再回头，打卡本（visited）防回头路；连通块 = 每个未访问顶点开新轮，找路答"能不能到"——最短路找 BFS。