目录
在上一篇文章中，我们介绍了图的存储结构，特别是常见的邻接矩阵和邻接表，并重点强调了邻接表在图算法实现中的高效性和广泛应用。图是一种高度抽象的数据结构，它不仅可以描述社交网络中的好友关系、交通系统中的道路连通情况，还能刻画任务调度中的依赖关系、程序分析中的调用图以及知识图谱中的语义关系。
然而，光有图的存储结构还远远不够。要真正发挥图模型的价值，我们需要在图上进行各种操作，其中最基础、最常用的操作就是 图的遍历（Graph Traversal）。遍历的目标是从一个或多个顶点出发，按照一定的规则访问图中所有可达的顶点，并在访问过程中提取有价值的信息。遍历不仅是理解图结构的第一步，更是许多高级图算法的基石。
因此，图遍历不仅仅是一个技术细节，而是图论和算法中一个极为核心的操作。本文将详细介绍两种最经典的遍历方式：深度优先搜索（DFS）和广度优先搜索（BFS），并结合上节课中给出的邻接表存储结构，即adjacency.AdjacencyGraph，给出 Java 风格的代码实现与应用场景分析。
一 深度优先搜索（DFS）
1.1 基本思想
深度优先搜索（Depth First Search，DFS）是一种沿着图的分支不断深入的遍历策略。它的基本过程是：
从一个起始顶点出发，将其标记为“已访问”；
访问该顶点的一个未被访问的邻接点；
递归或迭代地继续深入，直到无法再前进；
回溯到上一个顶点，继续寻找其他未访问的邻接点；
重复上述过程，直到所有可达顶点都被访问。
DFS 的思想与“走迷宫”很相似：始终沿着一条路径走到底，若走不下去，则返回到分叉点，尝试其他路径。
1.2 算法特点
搜索深入：优先向深层探索，往往能快速找到一条路径。
回溯特性：当路径走到尽头时，会退回上一步继续探索。
空间效率高：递归栈或显式栈存储访问路径，通常空间复杂度为 O(V)，其中 V 是顶点数。
1.3 伪代码
DFS 可以用递归和非递归两种方式实现。伪代码如下：
递归版（隐式栈）：
DFS(u): 标记 u 已访问 for 每个 u 的邻接点 v: if v 未访问: DFS(v)
非递归版（显示栈）：
DFS(u): 初始化栈 stack push(u) while stack 非空: v = pop() if v 未访问: 标记 v 已访问 for v 的所有邻接点 w: if w 未访问: push(w)
1.4 Java 风格代码实现
假设我们已经有邻接表 AdjacencyGraph 的实现，支持 getNeighbors(int v) 返回某顶点的邻接点列表。下面给出 DFS 的 Java 风格实现。
import org.algds.graph.adjacency.AdjacencyGraph;
import org.algds.graph.adjacency.Edge;
import org.algds.graph.adjacency.Label;
import org.algds.graph.adjacency.Vertex;
import java.util.*;
public class DepthFirstSearch {
/**
* 递归DFS（隐式栈）
*
* @param graph
* @param start
*/
public static void dfsRecursive(AdjacencyGraph graph, Vertex start) {
System.out.print("递归DFS遍历顺序：");
dfs(graph, start, new HashSet<>());
System.out.println();
}
public static void dfs(AdjacencyGraph graph, Vertex start,Set<Integer> visited) {
if (start == null) {
return;
}
visited.add(start.getId());
System.out.print(start.getName() + " ");
for (Edge edge : start.getEdgeList()) {
Vertex neighbor = edge.getTo();
if (!visited.contains(neighbor.getId())) {
dfs(graph,neighbor,visited);
}
}
}
/**
* 非递归DFS（显式栈）
*
* @param graph
* @param start
*/
public static void dfsIterative(AdjacencyGraph graph, Vertex start) {
if (start == null) {
return;
}
Set<Integer> visited = new HashSet<>();
Deque<Vertex> stack = new ArrayDeque<>();
stack.push(start);
System.out.print("显式栈DFS遍历顺序：");
while (!stack.isEmpty()) {
Vertex v = stack.pop();
if (!visited.contains(v.getId())) {
visited.add(v.getId());
System.out.print(v.getName() + " ");
// 倒序入栈以保持与递归顺序一致
List<Edge> edges = v.getEdgeList();
for (int i = edges.size() - 1; i >= 0; i--) {
Vertex neighbor = edges.get(i).getTo();
if (!visited.contains(neighbor.getId())) {
stack.push(neighbor);
}
}
}
}
System.out.println();
}
/**
* 主函数测试
*
* A
* / \
* B C
* | \
* D E
*
* @param args
*/
public static void main(String[] args) {
// 构建图
AdjacencyGraph graph = new AdjacencyGraph();
// 创建标签
Label vertexLabel = new Label("V", 1);
Label edgeLabel = new Label("E", 2);
// 创建顶点
Vertex A = new Vertex("A", vertexLabel);
Vertex B = new Vertex("B", vertexLabel);
Vertex C = new Vertex("C", vertexLabel);
Vertex D = new Vertex("D", vertexLabel);
Vertex E = new Vertex("E", vertexLabel);
// 添加顶点
graph.addVertex(A);
graph.addVertex(B);
graph.addVertex(C);
graph.addVertex(D);
graph.addVertex(E);
// 添加无向边（使用双向边模拟）
graph.addEdge(new Edge(A, B, 1, edgeLabel));
graph.addEdge(new Edge(B, A, 1, edgeLabel));
graph.addEdge(new Edge(A, C, 1, edgeLabel));
graph.addEdge(new Edge(C, A, 1, edgeLabel));
graph.addEdge(new Edge(B, D, 1, edgeLabel));
graph.addEdge(new Edge(D, B, 1, edgeLabel));
graph.addEdge(new Edge(C, E, 1, edgeLabel));
graph.addEdge(new Edge(E, C, 1, edgeLabel));
// 打印顶点和边的数量
System.out.println(String.format("顶点数量 %s",graph.getVertexNum()));
System.out.println(String.format("边的数量 %s",graph.getEdgeNum()));
// 执行DFS遍历
dfsRecursive(graph, A); // 递归DFS
dfsIterative(graph, A); // 显式栈DFS
}
}
测试结果:
顶点数量 5 边的数量 8 递归DFS遍历顺序：A B D C E 显式栈DFS遍历顺序：A B D C E
1.5 应用场景
连通性检测：判断一个图是否连通，只需从某个顶点执行 DFS，看能否访问所有顶点。
拓扑排序：在有向无环图（DAG）中，利用 DFS 可以得到拓扑序列。
环检测：在 DFS 过程中，如果遇到已访问但仍在递归栈中的顶点，则存在环。
路径搜索：在迷宫或棋盘中寻找一条路径，DFS 能快速探索出完整路径。
二 广度优先搜索（BFS）
2.1 基本思想
广度优先搜索（Breadth First Search，BFS）是一种分层遍历策略。其过程是：
从起始顶点出发，将其加入队列并标记为已访问；
依次从队列中取出顶点，访问它的所有未访问邻接点，并将这些邻接点入队；
重复此过程，直到队列为空。
BFS 的思想类似“水波扩散”：先访问离起点最近的一层顶点，再访问下一层，逐层向外扩展。
2.2 算法特点
分层遍历：访问顺序与顶点到起点的距离一致。
最短路径保证：在无权图中，BFS 能保证找到从起点到其他顶点的最短路径。
空间复杂度较高：需要队列存储每层顶点，最坏情况空间复杂度为 O(V) + O(E)。
2.3 伪代码
BFS(u): 初始化队列 queue 标记 u 已访问并入队 while queue 非空: v = 出队 访问 v for v 的所有邻接点 w: if w 未访问: 标记 w 已访问 入队 w
2.4 Java 风格代码实现
import org.algds.graph.adjacency.AdjacencyGraph;
import org.algds.graph.adjacency.Edge;
import org.algds.graph.adjacency.Label;
import org.algds.graph.adjacency.Vertex;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class BreadthFirstSearch {
/**
* BFS实现：使用队列
*/
public static void bfs(AdjacencyGraph graph, Vertex start) {
if (start == null) {
return;
}
Set<Integer> visited = new HashSet<>(); // 已访问集合
Queue<Vertex> queue = new LinkedList<>(); // 队列实现BFS
queue.offer(start);
visited.add(start.getId());
System.out.print("BFS遍历顺序：");
while (!queue.isEmpty()) {
Vertex v = queue.poll();
System.out.print(v.getName() + " ");
for (Edge edge : v.getEdgeList()) {
Vertex neighbor = edge.getTo();
if (!visited.contains(neighbor.getId())) {
visited.add(neighbor.getId());
queue.offer(neighbor);
}
}
}
System.out.println();
}
/**
* 主函数测试
* A
* / \
* B C
* | \
* D E
* @param args
*/
public static void main(String[] args) {
// 构建图
AdjacencyGraph graph = new AdjacencyGraph();
// 创建标签
Label vertexLabel = new Label("V", 1);
Label edgeLabel = new Label("E", 2);
// 创建顶点
Vertex A = new Vertex("A", vertexLabel);
Vertex B = new Vertex("B", vertexLabel);
Vertex C = new Vertex("C", vertexLabel);
Vertex D = new Vertex("D", vertexLabel);
Vertex E = new Vertex("E", vertexLabel);
// 添加顶点
graph.addVertex(A);
graph.addVertex(B);
graph.addVertex(C);
graph.addVertex(D);
graph.addVertex(E);
// 添加无向边（使用双向边模拟）
graph.addEdge(new Edge(A, B, 1, edgeLabel));
graph.addEdge(new Edge(B, A, 1, edgeLabel));
graph.addEdge(new Edge(A, C, 1, edgeLabel));
graph.addEdge(new Edge(C, A, 1, edgeLabel));
graph.addEdge(new Edge(B, D, 1, edgeLabel));
graph.addEdge(new Edge(D, B, 1, edgeLabel));
graph.addEdge(new Edge(C, E, 1, edgeLabel));
graph.addEdge(new Edge(E, C, 1, edgeLabel));
// 打印顶点和边的数量
System.out.println(String.format("顶点数量 %s",graph.getVertexNum()));
System.out.println(String.format("边的数量 %s",graph.getEdgeNum()));
// 执行BFS
bfs(graph, A);
}
}
测试结果
顶点数量 5 边的数量 8 BFS遍历顺序：A B C D E
2.5 应用场景
最短路径搜索：在无权图中，BFS 保证找到的路径一定是最短的。
分层结构分析：适用于社交网络的“好友关系层次”，或树形层次结构遍历。
广度优先匹配：在二分图匹配中，BFS 用于构建分层图。
传播问题模拟：模拟病毒传播、信息扩散等，都可以用 BFS 建模。
三 DFS 与 BFS 的对比
| 特性 | DFS | BFS |
|---|---|---|
| 遍历策略 | 沿着一条路径深入，直到不能再走为止 | 分层逐层访问，像水波扩散 |
| 数据结构 | 栈（隐式栈或显式栈） | 队列 |
| 时间复杂度 | O(V+E) | O(V+E) |
| 空间复杂度 | O(V)（递归深度或栈空间） | O(V+E)（队列可能存储大量顶点） |
| 应用场景 | 拓扑排序、环检测、路径枚举 | 最短路径、层次分析、传播模拟 |
| 遍历顺序特点 | 不唯一，依赖邻接表中邻居顺序 | 固定层次，结果更直观 |
总结：
DFS 偏向“纵向探索”，适合寻找路径和结构性质；
BFS 偏向“横向扩展”，适合最短路径和层次分析；
两者互为补充，常常结合使用。例如，在求最短路径时 BFS 更合适，而在检测环时 DFS 更高效。
四 遍历的价值与扩展
图的遍历不仅仅是一种基础操作，更是后续复杂图算法的核心支撑：
最短路径算法（Dijkstra、Bellman-Ford）：基于 BFS 思想在加权图上的扩展。
最小生成树（Prim、Kruskal）：需要遍历图结构以保证覆盖所有顶点。
强连通分量（Tarjan、Kosaraju）：基于 DFS 的递归回溯特性。
网络流与匹配问题：BFS 用于层次图的构造，DFS 用于寻找增广路径。
可以说，任何一个复杂的图算法，几乎都离不开遍历的影子。学习 DFS 和 BFS，不仅是掌握图论的入门技能，更是通向更高阶算法的必经之路。
五 图遍历回顾
本文介绍了两种最经典的遍历方式：深度优先搜索（DFS）和广度优先搜索（BFS）。我们给出了基于邻接表存储结构的 Java 风格实现，并通过分析两种算法的思想、特点和应用场景，揭示了它们在图论中的重要地位。
DFS 注重“深度”，擅长发现结构特征，如环、路径；BFS 注重“广度”，擅长层次分析和最短路径搜索。两者相辅相成，共同构成了图算法世界的基石。未来在学习更复杂的图算法时，几乎每一个算法都能追溯到 DFS 或 BFS 的思想。因此，熟练掌握这两种遍历方法，是深入学习图论与算法的重要前提。