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开始搜索  }  
}

应用场景

1. 路径查找：寻找从源节点到目标节点的路径，例如迷宫问题。
2. 图的连通性：判断图中两个节点是否在同一个连通分量中。
3. 拓扑排序：在有向无环图中进行节点排序，常用于任务调度。
4. 强连通分量（Kosaraju算法或Tarjan算法）：处理有向图中强连通分量的查找。
5. 拼图解法：例如八数码问题，可以使用 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("没有找到路径。");  }  }  
}

 

1. 迷宫表示：

   • 迷宫使用二维数组 maze 表示，0 代表可以通行，1 代表墙壁。

2. 定义方向：

   • DIRECTIONS 数组定义了四个移动方向（下、右、上、左）。

3. DFS 寻找路径：

   • solve 方法是实现 DFS 的核心：
     • 检查当前位置的有效性（边界检查、是否是墙、是否已访问）。
     • 将当前位置标记为已访问，并添加到路径中。
     • 如果找到终点，则返回成功。
     • 通过递归尝试四个方向的移动。
     • 如果未找到路径，则回溯，移除最后的步骤。

4. 主函数：

   • 初始化迷宫并调用 solve 方法解决迷宫。
   • 如果找到了一条路径，打印路径。

 

注意事项

• 时间复杂度：DFS 的时间复杂度是 O(V + E)，V 是节点数，E 是边数，因为每个节点和每条边都只被访问一次。
• 空间复杂度：若使用递归，最坏情况下（即图是链状结构）空间复杂度为 O(V)。如果使用显式栈，空间复杂度也是 O(V)，最坏情况下（栈的深度达到 V）。
• 避免重复访问：使用集合来存储已访问的节点，确保每个节点只被访问一次。
• 处理图的变化：对于动态变化的图结构，可能需要重复调用 DFS 方法来更新状态