GESP 七级 · GESP 202603 C++ 七级 第 25 题

在一个无向连通图中，从任意顶点开始进行深度优先遍历，最终得到的 DFS 生成树一定包含图中的所有顶点。

DFS 使用栈（或递归），沿一条路径走到底再回溯，适合遍历所有可能状态。注意回溯时的状态恢复。

DFS 递归遍历时注意状态回溯（恢复现场）。图遍历需要visited数组避免重复访问和死循环。

【考点】DFS 生成树｜连通图性质

1. 🎯 考纲定位 在GESP七级《算法》模块，这可是图论基础里的送分项！命题人专门卡住那些以为DFS只遍历一部分点的学生，用连通图这个前提直接戳穿"生成树会漏点"的幻觉。

2. 🧠 解题思维 看到题先盯死"无向连通图"三个字——连通意味着每点都可达。DFS从起点出发，栈里存着"待访问"队列，只要图没走完就不断弹出栈顶、访问新邻接点。因为图是连通的，所有点都会被推到栈里（或递归调用栈里）。生成树定义就是DFS访问经过的边构成的树，既然全点都访问了，树的顶点集自然等于原图顶点集。

3. 🪤 陷阱拆解 错误选项B想让你掉进"生成树≠原图"的坑里，故意用"一定"这种绝对词制造不安全感——其实连通图DFS生成树就是包含所有点的，这是定理级结论。学生容易把DFS当成BFS或者只遍历部分点，但"连通"二字把范围锁死了。

4. 🔄 反命题思维 反推一下：如果图改成"非连通"，DFS生成树就只含一个连通分量里的点；如果问"生成树边数"，答案是V-1；如果问"DFS树高度"，那得看具体结构。刷到"DFS生成树"题，先问自己：图连不连？起点在哪？生成的边集算不算树？