图的遍历是图论中最基础也是最重要的操作之一。无论是社交网络分析、地图导航，还是编译器中的依赖分析，都离不开对图的系统性遍历。本文将用Java完整实现广度优先搜索（BFS）与深度优先搜索（DFS），并在此基础上实现连通分量检测、环路判断等实用功能。
一、算法原理
1.1 深度优先搜索（DFS）
DFS沿着一条路径尽可能深入地探索，直到无法继续时才回溯。其核心思想是”走到底再回头”。DFS通常使用递归或显式栈实现，时间复杂度为O(V+E)，空间复杂度为O(V)。
1.2 广度优先搜索（BFS）
BFS从起点出发，逐层向外扩展，先访问所有距离为1的节点，再访问距离为2的节点，以此类推。BFS通常使用队列实现，天然适合求解最短路径问题（无权图）。时间复杂度同样为O(V+E)。
1.3 连通分量
在无向图中，连通分量是指图中极大的连通子图。通过一次DFS或BFS可以遍历一个连通分量中的所有节点。对每个未访问的节点启动一次遍历，即可统计出所有连通分量。
二、Java实现
import java.util.*;
/**
* 图的遍历系统实现
* 支持BFS、DFS、连通分量检测、环路检测
*/
public class GraphTraversal {
// 邻接表表示的无向图
private final int vertices;
private final List<List<Integer>> adjacencyList;
public GraphTraversal(int vertices) {
this.vertices = vertices;
this.adjacencyList = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
adjacencyList.add(new ArrayList<>());
}
}
/**
* 添加无向边
*/
public void addEdge(int u, int v) {
adjacencyList.get(u).add(v);
adjacencyList.get(v).add(u);
}
/**
* 深度优先搜索（递归实现）
* @param start 起始顶点
* @return 遍历顺序列表
*/
public List<Integer> dfsRecursive(int start) {
boolean[] visited = new boolean[vertices];
List<Integer> result = new ArrayList<>();
dfsHelper(start, visited, result);
return result;
}
private void dfsHelper(int vertex, boolean[] visited, List<Integer> result) {
visited[vertex] = true;
result.add(vertex);
// 遍历当前顶点的所有邻接点
for (int neighbor : adjacencyList.get(vertex)) {
if (!visited[neighbor]) {
dfsHelper(neighbor, visited, result);
}
}
}
/**
* 深度优先搜索（迭代实现，显式栈）
* @param start 起始顶点
* @return 遍历顺序列表
*/
public List<Integer> dfsIterative(int start) {
boolean[] visited = new boolean[vertices];
List<Integer> result = new ArrayList<>();
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int vertex = stack.pop();
if (!visited[vertex]) {
visited[vertex] = true;
result.add(vertex);
// 将未访问的邻接点入栈
for (int neighbor : adjacencyList.get(vertex)) {
if (!visited[neighbor]) {
stack.push(neighbor);
}
}
}
}
return result;
}
/**
* 广度优先搜索
* @param start 起始顶点
* @return 遍历顺序列表
*/
public List<Integer> bfs(int start) {
boolean[] visited = new boolean[vertices];
List<Integer> result = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int vertex = queue.poll();
result.add(vertex);
// 将未访问的邻接点入队
for (int neighbor : adjacencyList.get(vertex)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
return result;
}
/**
* BFS求最短路径（无权图）
* @param start 起点
* @param end 终点
* @return 最短路径上的顶点列表，如果不存在则返回空列表
*/
public List<Integer> shortestPath(int start, int end) {
boolean[] visited = new boolean[vertices];
int[] parent = new int[vertices];
Arrays.fill(parent, -1);
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int vertex = queue.poll();
if (vertex == end) {
// 重建路径
List<Integer> path = new ArrayList<>();
int current = end;
while (current != -1) {
path.add(current);
current = parent[current];
}
Collections.reverse(path);
return path;
}
for (int neighbor : adjacencyList.get(vertex)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
parent[neighbor] = vertex;
queue.offer(neighbor);
}
}
}
return Collections.emptyList(); // 无法到达
}
/**
* 检测无向图中是否存在环
* @return true如果存在环
*/
public boolean hasCycle() {
boolean[] visited = new boolean[vertices];
for (int i = 0; i < vertices; i++) {
if (!visited[i]) {
if (hasCycleDFS(i, -1, visited)) {
return true;
}
}
}
return false;
}
private boolean hasCycleDFS(int vertex, int parent, boolean[] visited) {
visited[vertex] = true;
for (int neighbor : adjacencyList.get(vertex)) {
if (!visited[neighbor]) {
if (hasCycleDFS(neighbor, vertex, visited)) {
return true;
}
} else if (neighbor != parent) {
// 访问到已访问的节点且不是父节点，说明有环
return true;
}
}
return false;
}
/**
* 查找所有连通分量
* @return 每个连通分量的顶点列表
*/
public List<List<Integer>> findConnectedComponents() {
boolean[] visited = new boolean[vertices];
List<List<Integer>> components = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
if (!visited[i]) {
List<Integer> component = new ArrayList<>();
dfsComponent(i, visited, component);
components.add(component);
}
}
return components;
}
private void dfsComponent(int vertex, boolean[] visited, List<Integer> component) {
visited[vertex] = true;
component.add(vertex);
for (int neighbor : adjacencyList.get(vertex)) {
if (!visited[neighbor]) {
dfsComponent(neighbor, visited, component);
}
}
}
/**
* 二分图检测（BFS实现）
* @return true如果是二分图
*/
public boolean isBipartite() {
int[] color = new int[vertices];
Arrays.fill(color, -1); // -1表示未着色
for (int start = 0; start < vertices; start++) {
if (color[start] != -1) continue;
Queue<Integer> queue = new LinkedList<>();
color[start] = 0;
queue.offer(start);
while (!queue.isEmpty()) {
int vertex = queue.poll();
for (int neighbor : adjacencyList.get(vertex)) {
if (color[neighbor] == -1) {
color[neighbor] = 1 - color[vertex];
queue.offer(neighbor);
} else if (color[neighbor] == color[vertex]) {
return false; // 相邻节点颜色相同，不是二分图
}
}
}
}
return true;
}
// 主方法：演示所有功能
public static void main(String[] args) {
GraphTraversal graph = new GraphTraversal(8);
// 构建示例图
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(3, 6);
graph.addEdge(4, 6);
graph.addEdge(5, 7);
System.out.println("=== DFS递归遍历 ===");
System.out.println(graph.dfsRecursive(0));
System.out.println("\n=== DFS迭代遍历 ===");
System.out.println(graph.dfsIterative(0));
System.out.println("\n=== BFS遍历 ===");
System.out.println(graph.bfs(0));
System.out.println("\n=== 最短路径(0->6) ===");
System.out.println(graph.shortestPath(0, 6));
System.out.println("\n=== 连通分量 ===");
System.out.println(graph.findConnectedComponents());
System.out.println("\n=== 是否存在环 ===");
System.out.println(graph.hasCycle());
System.out.println("\n=== 是否为二分图 ===");
System.out.println(graph.isBipartite());
}
}
三、复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| DFS（递归/迭代） | O(V + E) | O(V) |
| BFS | O(V + E) | O(V) |
| 最短路径（无权图） | O(V + E) | O(V) |
| 连通分量检测 | O(V + E) | O(V) |
| 环路检测 | O(V + E) | O(V) |
| 二分图检测 | O(V + E) | O(V) |
其中V为顶点数，E为边数。所有操作都需要遍历全图一次，因此时间复杂度均为线性。
四、应用场景
- 社交网络分析：发现用户群体、社区结构
- 地图导航：无权图最短路径、连通性判断
- 编译器优化：检测循环依赖、模块引用关系
- 网络爬虫：按层级抓取网页（BFS）或深度抓取（DFS）
- 游戏开发：迷宫求解、状态空间搜索
五、总结
本文系统实现了图的两种基本遍历方式BFS与DFS，并在此基础上扩展了最短路径、连通分量、环路检测和二分图判定等实用功能。掌握这些基础算法是深入学习图论和解决复杂网络问题的前提。
