Java实现图的深度优先搜索：核心代码与实用教程

关键词：Java图遍历、DFS算法、邻接表实现、递归与非递归、应用场景
描述：本文详解Java中深度优先搜索(DFS)的4种实现方式，包含完整的邻接表建图代码和真实项目中的优化技巧。

一、深度优先搜索的核心原理

深度优先搜索(DFS)就像走迷宫时优先探索单条路径到底的策略。当遇到死路时，回溯到最近的分叉点继续探索。这种"不撞南墙不回头"的特性，使其特别适合解决连通性问题、拓扑排序等场景。

二、Java实现图的两种存储方式

2.1 邻接矩阵实现

java
class GraphMatrix {
private int[][] matrix;
private int vertexCount;

public GraphMatrix(int vertexCount) {
    this.matrix = new int[vertexCount][vertexCount];
    this.vertexCount = vertexCount;
}

public void addEdge(int src, int dest) {
    matrix[src][dest] = 1;
    matrix[dest][src] = 1; // 无向图需双向添加
}

}

2.2 邻接表实现（更节省空间）

java
class GraphList {
private LinkedList[] adjList;

public GraphList(int vertexCount) {
    adjList = new LinkedList[vertexCount];
    for (int i = 0; i < vertexCount; i++) {
        adjList[i] = new LinkedList<>();
    }
}

public void addEdge(int src, int dest) {
    adjList[src].add(dest);
    adjList[dest].add(src); // 无向图需双向添加
}

}

三、DFS的四种实现方式

3.1 递归实现（最简洁）

java
void dfsRecursive(int v, boolean[] visited, GraphList graph) {
visited[v] = true;
System.out.print(v + " ");

for (int neighbor : graph.adjList[v]) {
    if (!visited[neighbor]) {
        dfsRecursive(neighbor, visited, graph);
    }
}

}

3.2 栈实现（避免递归溢出）

java
void dfsStack(int start, GraphList graph) {
Stack stack = new Stack<>();
boolean[] visited = new boolean[graph.vertexCount];

stack.push(start);
visited[start] = true;

while (!stack.isEmpty()) {
    int current = stack.pop();
    System.out.print(current + " ");

    for (int neighbor : graph.adjList[current]) {
        if (!visited[neighbor]) {
            stack.push(neighbor);
            visited[neighbor] = true;
        }
    }
}

}

3.3 带路径记录的实现

java
List<List> dfsWithPaths(GraphList graph) {
List<List> paths = new ArrayList<>();
boolean[] visited = new boolean[graph.vertexCount];

for (int i = 0; i < graph.vertexCount; i++) {
    if (!visited[i]) {
        Stack<Integer> path = new Stack<>();
        dfsPathHelper(i, visited, graph, path, paths);
    }
}
return paths;

}

void dfsPathHelper(int v, boolean[] visited,
GraphList graph, Stack path,
List<List> paths) {
visited[v] = true;
path.push(v);

if (graph.adjList[v].isEmpty()) {
    paths.add(new ArrayList<>(path));
} else {
    for (int neighbor : graph.adjList[v]) {
        if (!visited[neighbor]) {
            dfsPathHelper(neighbor, visited, graph, path, paths);
        }
    }
}

path.pop();

}

3.4 处理大型图的迭代深化DFS

java
void iddfs(GraphList graph, int start, int maxDepth) {
for (int depth = 0; depth <= maxDepth; depth++) {
boolean[] visited = new boolean[graph.vertexCount];
dfsWithDepth(start, visited, graph, depth);
}
}

void dfsWithDepth(int v, boolean[] visited,
GraphList graph, int depth) {
if (depth < 0) return;

visited[v] = true;
System.out.print(v + " ");

for (int neighbor : graph.adjList[v]) {
    if (!visited[neighbor]) {
        dfsWithDepth(neighbor, visited, graph, depth - 1);
    }
}

}

四、实际开发中的优化技巧

1. 剪枝优化：在搜索树中提前终止不可能的分支
   java if (currentPath.size() > minPathLength) { return; // 提前终止 }

2. 双向DFS：当知道目标节点时，从起点和终点同时搜索

3. 记忆化搜索：存储已计算子问题的结果java
   Map<Integer, Integer> memo = new HashMap<>();

int dfsWithMemo(int v) {
if (memo.containsKey(v)) {
return memo.get(v);
}
// ...计算逻辑
memo.put(v, result);
return result;
}

1. 并行DFS：对独立子树使用多线程处理

五、常见问题解决方案

1. 栈溢出处理：改用显式栈结构或设置最大递归深度
2. 环检测：通过记录当前路径上的节点
3. 性能瓶颈：改用迭代实现或采用更高效的数据结构
4. 多连通分量：外层循环检查未访问节点

完整项目示例建议结合JGraphT库实现生产级图算法，该库提供了优化的DFS实现和丰富的图分析工具。