Java实现DFS深度优先搜索算法的2个示例

最近和算法杠上了，现在来看下DFS。

深度优先搜索（DFS，Depth-First Search）是一种图遍历算法，主要用于在图中找到所有路径、检测连通性、以及应用在树和图的许多遍历问题上。

与广度优先搜索（BFS）的“逐层扩展”不同，DFS 更倾向于“沿路径深入”，也就是说，DFS 会优先深入一个节点的子节点，直到到达尽头再回溯。

一、DFS 的核心概念

DFS 的主要特点是优先沿一个路径“深入”图的最深处，直到无法继续，然后回溯到上一个节点再继续深入新的路径。DFS 适用于需要探索所有可能路径的场景，比如树的遍历、路径查找等。

DFS 可以通过递归或栈来实现，因为递归本质上也利用了栈结构。无论是递归还是栈实现，DFS 的遍历过程都是通过“先访问一个节点的子节点，再访问兄弟节点”来完成的。

二、DFS 的实现步骤

假设我们有一个简单的图结构如下：

1

/ \

2 3

/ \ \

4 5 6

DFS 的实现通常可以分为以下几个步骤：

访问起始节点：将起始节点标记为已访问。

递归或利用栈访问每个邻居节点：对于起始节点的每一个邻居节点，继续重复访问，直到所有节点都被访问。

回溯：当访问到一个节点的所有子节点后，回溯到上一个节点，再继续访问其他未被访问的邻居节点。

如果我们从节点 1 开始执行 DFS，可能的遍历顺序有多种，比如 1 -> 2 -> 4 -> 5 -> 3 -> 6。

DFS 并不保证遍历顺序，所以可能会有不同的深度路径结果。

三、递归实现 DFS

import java.util.*;

public class DFSExample {

// 深度优先搜索的递归方法

public static void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {

if (visited.contains(node)) {

return; // 如果节点已经访问过，直接返回

}

System.out.println("Visited: " + node); // 访问节点

visited.add(node); // 标记节点已访问

// 递归访问该节点的所有邻居

for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {

dfs(graph, neighbor, visited);

}

}

public static void main(String[] args) {

// 示例图：邻接列表表示

Map<Integer, List<Integer>> graph = new HashMap<>();

graph.put(1, Arrays.asList(2, 3));

graph.put(2, Arrays.asList(4, 5));

graph.put(3, Arrays.asList(6));

graph.put(4, Arrays.asList());

graph.put(5, Arrays.asList());

graph.put(6, Arrays.asList());

Set<Integer> visited = new HashSet<>(); // 记录访问过的节点

dfs(graph, 1, visited); // 从节点 1 开始 DFS

}

}

在这个代码中：

graph 集合用于图的邻接列表表示。

visited 集合用于记录已访问的节点，以避免重复访问。

dfs 方法是递归的深度优先搜索，从起始节点开始，依次访问其邻居。

运行结果：

Visited: 1

Visited: 2

Visited: 4

Visited: 5

Visited: 3

Visited: 6

四、DFS 的非递归实现

除了递归，DFS 也可以使用栈来实现：

import java.util.*;

public class DFSExample {

public static void dfsStack(Map<Integer, List<Integer>> graph, int start) {

Stack<Integer> stack = new Stack<>();

Set<Integer> visited = new HashSet<>();

stack.push(start); // 起始节点入栈

while (!stack.isEmpty()) {

int node = stack.pop(); // 取出栈顶节点

if (!visited.contains(node)) {

System.out.println("Visited: " + node);

visited.add(node); // 标记节点已访问

// 将该节点的所有未访问邻居压入栈

for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {

if (!visited.contains(neighbor)) {

stack.push(neighbor);

}

}

}

}

}

public static void main(String[] args) {

// 示例图：邻接列表表示

Map<Integer, List<Integer>> graph = new HashMap<>();

graph.put(1, Arrays.asList(2, 3));

graph.put(2, Arrays.asList(4, 5));

graph.put(3, Arrays.asList(6));

graph.put(4, Arrays.asList());

graph.put(5, Arrays.asList());

graph.put(6, Arrays.asList());

dfsStack(graph, 1); // 从节点 1 开始 DFS

}

}

在非递归实现中，我们使用栈手动进行深度优先搜索，避免了递归的开销。

运行结果：

Visited: 1

Visited: 3

Visited: 6

Visited: 2

Visited: 5

Visited: 4

五、DFS 的应用场景

DFS 在很多图和树的场景中都很有用：

路径查找：DFS 可以找到图中从起点到终点的所有路径。

拓扑排序：在有向无环图（DAG）中，DFS 可以用来生成拓扑排序。

检测环：在无向图中，可以利用 DFS 来检测是否存在环。

连通性检测：在无向图中，DFS 可以找到图中的连通分量。

树的遍历：DFS 是二叉树的先序、中序和后序遍历的核心算法。

解决迷宫问题：DFS 可以用来找到迷宫中的一条路径（未必是最短路径）。

六、DFS 的时间复杂度和空间复杂度

假设图的节点数为 V，边数为 E，则：

时间复杂度：O(V + E)，因为每个节点和边最多访问一次。

空间复杂度：O(V)，主要取决于递归栈（或手动栈）和 visited 集合的大小。

七、DFS 和 BFS 的对比

八、最后总结

DFS 使用递归或栈结构，优先沿路径深入到最深的节点。

适用于路径查找、检测连通性和环等问题。

相比 BFS，DFS 并不保证找到无权图的最短路径。