图遍历基础
一句话总结
图的遍历就是 多叉树遍历 的延伸，主要遍历方式还是深度优先搜索（DFS）和广度优先搜索（BFS）。
唯一的区别是，树结构中不存在环，而图结构中可能存在环，所以我们需要标记遍历过的节点，避免遍历函数在环中死循环。
核心内容
三种遍历场景
由于图结构的复杂性，可以细分为遍历图的三种场景，每种场景的代码实现略有不同：
| 场景 | 标记数组 | 标记位置 | 说明 |
|---|---|---|---|
| 遍历节点 | visited 一维数组 |
前序位置 | 确保每个节点只被遍历一次 |
| 遍历边 | visited 二维数组 |
for循环内部 | 确保每条边只被遍历一次 |
| 遍历路径 | onPath 数组 |
前序标记，后序撤销 | 记录当前路径，用于穷举所有路径 |
深度优先搜索（DFS）
图的 DFS 比多叉树遍历多了一个 visited 数组，用来记录被遍历过的节点，避免遇到环时陷入死循环。
为什么成环会导致死循环？
最简单的成环场景：1 <=> 2（双向边）。如果不标记遍历过的节点，遍历会陷入 1->2->1->2->... 无限递归。有了 visited 数组，第一次遍历到节点时标记，再次遇到已访问节点时直接返回，避免死循环。
基于邻接表/邻接矩阵的 DFS 代码框架：
// 遍历图的所有节点
void traverse(Graph graph, int s, boolean[] visited) {
// base case
if (s < 0 || s >= graph.size()) {
return;
}
if (visited[s]) {
// 防止死循环
return;
}
// 前序位置
visited[s] = true;
System.out.println("visit " + s);
for (Edge e : graph.neighbors(s)) {
traverse(graph, e.to, visited);
}
// 后序位置
}
时间复杂度：$O(E + V)$，其中 $E$ 是边的总数，$V$ 是节点的总数。
为什么是 $O(E + V)$ 而不是 $O(V)$？ 树结构中边的数量和节点数量近似相等，所以时间复杂度是 $O(N + N) = O(N)$。但图结构中任意两个节点之间都可以连接一条边，边的数量和节点的数量不再有特定关系，所以要同时考虑边和节点的数量。
遍历所有边（二维 visited 数组）
遍历所有边的场景并不多见，主要是计算欧拉路径时会用到。
核心思路：用二维 visited[u][v] 数组记录边 u->v 是否已被遍历，确保每条边只被遍历一次。
// 从起点 s 开始遍历图的所有边
void traverseEdges(Graph graph, int s, boolean[][] visited) {
if (s < 0 || s >= graph.size()) {
return;
}
for (Edge e : graph.neighbors(s)) {
if (visited[s][e.to]) {
continue;
}
visited[s][e.to] = true;
System.out.println("visit edge: " + s + " -> " + e.to);
traverseEdges(graph, e.to, visited);
}
}
缺点：时间复杂度 $O(E + V^2)$，空间复杂度 $O(V^2)$。在讲解 Hierholzer 算法计算欧拉路径时会有优化方法。
遍历所有路径（onPath 数组）
图结构与树结构不同：树结构中从根节点到任意节点的路径唯一；图结构中可能存在多条路径。
遍历所有路径需要用 onPath 数组：
- 前序位置：标记节点在路径上
- 后序位置：撤销标记（节点离开路径）
这种方式可以穷举从起点到所有可达节点的路径，是计算最短路径等图论问题的基础。
相关概念
⚠️ 内容不完整说明
本文通过 defuddle 提取，内容被截断在"遍历所有路径"部分，缺失内容可能包括：
- BFS 详细实现代码
- BFS 与 DFS 的完整对比
- onPath 数组的完整代码示例
- 可视化面板说明
原始文章链接：https://labuladong.online/zh/algo/data-structure-basic/graph-traverse-basic/