6.3.2 深度优先遍历

DFS 访问顶点后沿一个未访问邻居不断深入，走不通再回溯。递归依赖调用栈，非递归可用显式栈。非连通图同样需外层扫描所有顶点得到 DFS 森林。

手工状态

同图0-1,0-2,1-3,2-3，按小编号邻接，递归DFS输出0,1,3,2。到3后先发现2，再回溯；具体序列受邻接顺序影响。

结构与代码

void dfs(int u){seen[u]=1;for(int v:g[u])if(!seen[v])dfs(v);}

时间 O(V+E)，递归栈最坏 O(V)。有向图可用三色状态区分未访问、递归栈中、已完成，以检测回边。

正确性依据

每个顶点首次访问后标记，后续边不会触发重复递归；递归完成意味着其所有可达未访后代已处理。

错解反馈

递归后才标记会在环上无限；把DFS树边之外都称回边；认为遍历序列唯一。

迁移训练

有向边0→1,1→2,2→0，用三色DFS在哪条边发现环？答案处理2→0时0仍为灰色，发现回边。