Java-DFS(深度优先搜索）
原理
深度优先搜索的基本思路是从一个节点开始，依次访问它的每一个邻居节点，直到达到一个没有未被访问的邻居的节点为止。这个过程可以使用递归或者栈来实现。其特点是尽可能深入每一个分支，然后再回溯。
DFS算法常用于解决以下类型的问题：
- 路径搜索：在图中寻找一条特定路径。
- 图的连通性：判断图是否是连通的。
- 拓扑排序：在有向无环图（DAG）中，对节点进行排序。
- 强连通分量：找出一个有向图的强连通分量。
深度优先搜索的实现
1. 图的表示
在实际使用中，图的表示通常有以下几种方式：
- 邻接矩阵：适用于边较多的情况，但空间复杂度为 O(V^2)，其中 V 是节点数。
- 邻接表：适用于边较少的图，空间复杂度为 O(V + E)，其中 E 是边数。
在下面的示例中，我们使用邻接表来表示图，因为它存储效率更高，适合大多数情况。
2. 使用递归实现 DFS
以下是通过递归方式实现深度优先搜索的详细代码，并附带注释以帮助理解每个部分的功能
import java.util.*;
public class DepthFirstSearch {
private Map<Integer, List<Integer>> graph; // 图的邻接表
// 构造函数
public DepthFirstSearch() {
graph = new HashMap<>(); // 初始化图
}
// 添加边：从源节点到目标节点
public void addEdge(int source, int destination) {
graph.putIfAbsent(source, new ArrayList<>()); // 如果源节点不存在，则添加
graph.get(source).add(destination); // 添加目标节点到源节点的邻接表中
}
// 深度优先搜索的入口方法
public void dfs(int start) {
Set<Integer> visited = new HashSet<>(); // 用于记录访问过的节点
dfsHelper(start, visited); // 调用递归助手方法
}
// 递归助手方法
private void dfsHelper(int node, Set<Integer> visited) {
if (visited.contains(node)) return; // 如果节点已访问，则返回
visited.add(node); // 标记节点为已访问
System.out.println(node); // 访问并打印当前节点
// 遍历所有邻居节点
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
dfsHelper(neighbor, visited); // 递归访问邻居节点
}
}
public static void main(String[] args) {
DepthFirstSearch dfs = new DepthFirstSearch();
// 构建图：节点和边
dfs.addEdge(1, 2);
dfs.addEdge(1, 3);
dfs.addEdge(2, 4);
dfs.addEdge(2, 5);
dfs.addEdge(3, 6);
dfs.addEdge(3, 7);
System.out.println("深度优先搜索结果：");
dfs.dfs(1); // 从节点1开始搜索
}
}
3. 使用栈实现 DFS
栈的实现方式不直接依赖于系统的调用栈，这对于深度大、可能导致栈溢出的情况特别有用。以下是迭代实现的代码：
import java.util.*;
public class DepthFirstSearchIterative {
private Map<Integer, List<Integer>> graph; // 图的邻接表
// 构造函数
public DepthFirstSearchIterative() {
graph = new HashMap<>(); // 初始化图
}
// 添加边：从源节点到目标节点
public void addEdge(int source, int destination) {
graph.putIfAbsent(source, new ArrayList<>()); // 如果源节点不存在，则添加
graph.get(source).add(destination); // 添加目标节点到源节点的邻接表中
}
// 使用栈迭代实现深度优先搜索
public void dfsIterative(int start) {
Set<Integer> visited = new HashSet<>(); // 记录访问过的节点
Stack<Integer> stack = new Stack<>(); // 创建栈
stack.push(start); // 将起始节点压入栈
while (!stack.isEmpty()) { // 只要栈不为空，继续遍历
int node = stack.pop(); // 弹出栈顶元素
if (!visited.contains(node)) { // 如果该节点未被访问
visited.add(node); // 标记为已访问
System.out.println(node); // 访问并打印当前节点
// 将所有邻居节点压入栈中
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
stack.push(neighbor); // 压入栈
}
}
}
}
public static void main(String[] args) {
DepthFirstSearchIterative dfsIterative = new DepthFirstSearchIterative();
// 构建图：节点和边
dfsIterative.addEdge(1, 2);
dfsIterative.addEdge(1, 3);
dfsIterative.addEdge(2, 4);
dfsIterative.addEdge(2, 5);
dfsIterative.addEdge(3, 6);
dfsIterative.addEdge(3, 7);
System.out.println("深度优先搜索（迭代）结果：");
dfsIterative.dfsIterative(1); // 从节点1开始搜索
}
}应用场景
- 路径查找：寻找从源节点到目标节点的路径，例如迷宫问题。
- 图的连通性：判断图中两个节点是否在同一个连通分量中。
- 拓扑排序：在有向无环图中进行节点排序，常用于任务调度。
- 强连通分量（Kosaraju算法或Tarjan算法）：处理有向图中强连通分量的查找。
- 拼图解法：例如八数码问题，可以使用 DFS 搜索所有可能的状态直到找到目标状态。
让我们通过一个实际的例子来理解深度优先搜索（DFS）的应用场景。这次我们会用一个简单的迷宫问题来演示 DFS 的使用。
问题描述：迷宫寻路
想象一下，一个迷宫是一个二维网格，其中某些单元格是可通行的（代表放空格），而其他单元格是不可通行的（代表墙壁）。我们的任务是找到从起点到终点的路径。
迷宫示例
我们用下面的二维数组表示迷宫，其中 0 表示可通行，1 表示墙壁：
0 0 1 0 0
0 1 0 1 0
0 1 0 0 0
0 0 0 1 1
1 1 0 0 0
起点为 (0, 0)，终点为 (4, 4)。
使用 DFS 寻找路径的代码
下面是一个 Java 实现的 DFS 代码，通过递归方式在迷宫中寻找从起点到终点的路径。
import java.util.*;
public class MazeSolver {
private static final int[][] DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 四个方向：下、右、上、左
private int[][] maze;
private boolean[][] visited;
private List<int[]> path; // 存储路径
public MazeSolver(int[][] maze) {
this.maze = maze;
this.visited = new boolean[maze.length][maze[0].length]; // 初始化访问标记
this.path = new ArrayList<>(); // 初始化路径
}
public boolean solve(int x, int y, int endX, int endY) {
// 检查边界条件：如果超出迷宫或当前位置是墙或已访问过则返回false
if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length ||
maze[x][y] == 1 || visited[x][y]) {
return false;
}
visited[x][y] = true; // 标记为已访问
path.add(new int[]{x, y}); // 添加位置到路径
// 如果到达终点，则返回true
if (x == endX && y == endY) {
return true;
}
// 递归尝试四个方向
for (int[] direction : DIRECTIONS) {
int newX = x + direction[0];
int newY = y + direction[1];
if (solve(newX, newY, endX, endY)) {
return true; // 找到路径
}
}
// 如果没有找到路径，则回溯
path.remove(path.size() - 1); // 移除最后一个位置
return false; // 返回false，表示未找到路径
}
public List<int[]> getPath() {
return path; // 获取找到的路径
}
public static void main(String[] args) {
int[][] maze = {
{0, 0, 1, 0, 0},
{0, 1, 0, 1, 0},
{0, 1, 0, 0, 0},
{0, 0, 0, 1, 1},
{1, 1, 0, 0, 0}
};
MazeSolver solver = new MazeSolver(maze);
if (solver.solve(0, 0, 4, 4)) {
System.out.println("找到路径：");
for (int[] position : solver.getPath()) {
System.out.println(Arrays.toString(position));
}
} else {
System.out.println("没有找到路径。");
}
}
}
-
迷宫表示：
- 迷宫使用二维数组
maze表示，0代表可以通行，1代表墙壁。
- 迷宫使用二维数组
-
定义方向：
DIRECTIONS数组定义了四个移动方向（下、右、上、左）。
-
DFS 寻找路径：
solve方法是实现 DFS 的核心：- 检查当前位置的有效性（边界检查、是否是墙、是否已访问）。
- 将当前位置标记为已访问，并添加到路径中。
- 如果找到终点，则返回成功。
- 通过递归尝试四个方向的移动。
- 如果未找到路径，则回溯，移除最后的步骤。
-
主函数：
- 初始化迷宫并调用
solve方法解决迷宫。 - 如果找到了一条路径，打印路径。
- 初始化迷宫并调用
注意事项
- 时间复杂度：DFS 的时间复杂度是 O(V + E)，V 是节点数，E 是边数，因为每个节点和每条边都只被访问一次。
- 空间复杂度：若使用递归，最坏情况下（即图是链状结构）空间复杂度为 O(V)。如果使用显式栈，空间复杂度也是 O(V)，最坏情况下（栈的深度达到 V）。
- 避免重复访问：使用集合来存储已访问的节点，确保每个节点只被访问一次。
- 处理图的变化：对于动态变化的图结构，可能需要重复调用 DFS 方法来更新状态