第3章 侦察行军：图的遍历
第 3 章 · 侦察行军：图的遍历
章节摘要：地图已存进计算机，远征队派出侦察兵去摸清每一处据点。遍历是图算法世界里最基础的步法：从起点出发，访问所有可达顶点，且每个顶点只到一次。步法只有两种范式——深度优先搜索一路走到底再回头，像孤胆侦察兵钻巷道；广度优先搜索层层向外推，像撒开包围网逐圈收缩。它们分别孕育了回溯法与最短路这两大算法家族。本章把两种步法的实现、性质与适用边界讲透，这是后续所有战役的共同地基。
学习目标
阅读完本章，你应当能够：
- 手写深度优先搜索的递归版与显式栈版，并解释两者等价的原因。
- 手写广度优先搜索，用队列维护" frontier "，并从遍历树中还原各顶点的层次与最短跳数。
- 说明深度优先搜索的"发现时刻与完成时刻"如何支撑环检测、拓扑排序、割点判定。
- 解释广度优先搜索为何在无权图上等价于单源最短路算法。
- 用两种遍历分别求解"连通块计数"与"迷宫最短路"，并对结果差异给出解释。
核心概念速览
金句：图的算法千千万，底层步法只两种——栈的深潜与队列的扩散。
子章节导航
第 1 节"深度优先搜索：一往无前的侦察路线"从巷道侦察的场景切入，实现递归与迭代两种版本，讲清时间戳、回溯与生成树结构，并预演它在环检测（第 4 章）与拓扑排序（第 6 章）里的关键角色。
第 2 节"广度优先搜索：层层推进的包围网"演示队列如何保证"先发现先扩展"，证明层次与最短跳数的对应关系，把迷宫寻路、词梯谜题等经典问题一网打尽，并直接铺向第 5 章的加权最短路。
子章节之间的逻辑关系
一句话论点：深度优先负责"钻"，广度优先负责"围"；钻的结构记时间戳，围的结构记层次——两棵遍历树是同一张图在不同军令下的两种投影。
同一张图 同一起点 ┌─────┴─────┐ 深度优先 广度优先 栈 · 深潜 队列 · 扩散 │ │ 生成深优先树 生成广优先树 发现/完成时间戳 层次 = 最短跳数 │ │ 回溯/环检测/拓扑 无权最短路/层次分解
前置知识与后续延伸
前置：第 2 章的邻接表（遍历的计价方式直接依赖它）、Python 的列表与队列用法、递归的基本概念。
后续延伸：深度优先的时间戳在下一章的连通性与环检测中立即上岗；广度优先的"层次即距离"思想在第 5 章被推广为 Dijkstra 的优先队列；第 9 章的欧拉巡游与本章的回溯步法一脉相承。
学习建议与对比要诀
两种遍历代码都只有十几行，但真把它们学进骨头里，要靠对比与追问。建议做三件事。第一，同图双跑：任取一张十来个顶点的图，分别手推深度优先与广度优先的访问序，再把两个版本的父指针画成两棵树贴在一起看——同一张图、同一起点，栈给出深潜的窄条树、队列给出敦实的层状树，这种并置的视觉冲击是理解两族算法分野的捷径。第二，盯住容器：两套实现共享"染色加翻档案"的全部流程，唯一的差别是栈与队列。建议把代码复制两份并排，只把容器那一行标红——记住"接口相同、语义由容器决定"这条铁律，第 5 章 Dijkstra 把队列升级为优先队列时就再不会觉得突兀。第三，动手改坏它：故意把广度优先的 deque 换成栈，看"层次即最短跳数"何时开始失效；故意删掉入队时的染色、改成出队时染色，看重复入队如何把队列灌成气球——从故障反学正确性，比顺着读三遍代码都扎实。自测标准：给定一张小图与起点，你能在纸上两分钟内写出两种遍历的访问序，并指出各自的遍历树里哪条边不是树边，本章即可放心翻页。