6.3.2 深度优先搜索
原书定位
印刷页P222起,对应PDF第234页。下文为目视整理的知识提要;完整内容见原书对照。
DFS 从当前顶点沿未访问邻点不断深入,走不动时沿调用栈回退,继续考察其他邻点。可用递归或显式栈实现;记录首次发现边可形成 DFS 树或森林。
有向图判环应区分“正在递归路径中”和“已经完成”的顶点,指向递归路径中祖先的边说明有环;仅遇到已访问顶点不足以判环。无向图还要排除直接返回父结点的那条边。

深度优先生成森林,原书P223。
对应练习
关联知识
- 3.2 队列
- 3.3.3 栈在递归中的应用
- 5.3.1 二叉树的遍历
- 6.2.1 邻接矩阵法
- 6.2.2 邻接表法
- 6.3 图的遍历
- 6.3.1 广度优先搜索
- 6.3.3 图的遍历与图的连通性
- 6.4.4 拓扑排序
- 8.3.2 快速排序
原书对照
展开原书对照截图

