6.3.2 深度优先搜索

教材导航 · 第6章

原书定位

印刷页P222起,对应PDF第234页。下文为目视整理的知识提要;完整内容见原书对照。

DFS 从当前顶点沿未访问邻点不断深入,走不动时沿调用栈回退,继续考察其他邻点。可用递归或显式栈实现;记录首次发现边可形成 DFS 树或森林。

有向图判环应区分“正在递归路径中”和“已经完成”的顶点,指向递归路径中祖先的边说明有环;仅遇到已访问顶点不足以判环。无向图还要排除直接返回父结点的那条边。

深度优先生成森林

深度优先生成森林,原书P223。

对应练习

6.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P222,PDF第234页

原书对照,原书P223,PDF第235页