图遍历（DFS / BFS）
图遍历（Graph Traversal）是系统地访问图中所有顶点（或从某起点出发能到达的全部顶点）的核心算法，分两大范式：深度优先搜索 DFS（一条路走到黑再回溯）与广度优先搜索 BFS（一层一层向外扩）。它们是图算法的「两条腿」——几乎所有图问题（连通性、路径、最短路、拓扑、二分图、网格搜索）都建立在这两种遍历之上。DFS 用栈或递归（递归本质是系统栈）实现，擅长找路径、判连通、探测回路；BFS 用队列实现，天然带层序信息，因此是无权图最短路的唯一正解。两者配合 visited 数组防重复访问，复杂度都是 O(V+E)（每条边、每个顶点各访问常数次）。
图遍历的全部考点源于一个事实：图可能有环，所以必须标记 visited 防止死循环——这是它与树遍历（树无环）的根本差异。由此衍生出四大主题：①DFS 的递归与迭代（栈）实现（深入到底再回溯）；②BFS 的队列实现与层序（逐层扩展，天然最短路）；③网格图上的遍历（岛屿、迷宫用方向数组把二维坐标当节点）；④经典应用（连通分量计数、无权图最短路、拓扑排序、二分图染色）。本叶只讲遍历算法本身，图的存储（邻接矩阵/邻接表）在独立叶「图的表示」中讨论——遍历框架对两种存储都通用，只是「取邻居」的方式不同。
评价
优点
- 统一且普适：一套 DFS/BFS 框架几乎能解所有「可达性 / 路径 / 连通」类图问题，套路高度可复用
- 复杂度可控：用
visited去重后，DFS/BFS 都是 O(V+E)，每条边、每个顶点各访问常数次，是最优遍历 - BFS 天然最短路：在无权图（或等权图）上，BFS 的层序 = 到起点的距离，第一次访问即最短路，无需 Dijkstra
- DFS 探路顺手：递归写法极简，擅长找「任意路径」、判连通、探测环、拓扑排序的后序逆序
缺点
- 必须处理环：图有环时若无
visited会死循环（树遍历无此问题）——visited时机错了还会重复入队/爆内存 - DFS 可能栈溢出：递归 DFS 在深链状图（如十万节点的链）上会触发系统栈上限；需改迭代或手动调栈
- 不擅长带权最短路：DFS/BFS 都不处理边权，带权图要换 Dijkstra/Bellman-Ford
- 空间开销：BFS 队列最坏存 O(V) 个节点（呈扇形扩展时），DFS 递归深度最坏 O(V)——都是线性空间，但常数不容忽视
本叶地图
- 入门 —— DFS 与 BFS 的定义与直觉、visited 数组、复杂度 O(V+E)、适用场景对比（DFS 找路径/连通性，BFS 无权最短路）
- DFS 与 BFS 详解 —— DFS 递归框架与迭代（栈）框架、BFS 队列框架、邻接表/矩阵上的实现、网格问题方向数组、visited 时机
- 应用 —— 连通分量计数、无权图最短路径（BFS 层序）、拓扑排序（DFS/入度法）、二分图判定（DFS 染色）、网格 flood fill
- 参考 —— DFS/BFS 代码模板、复杂度表、网格方向数组、应用清单、易错点
交互演示
- 迷宫 DFS/BFS 可视化演示 —— 网格图上的 DFS 深入与 BFS 层序扩展对比