当前位置：首页 > news >正文

数据结构第25节深度优先搜索

news 来源：原创 2024/9/21 3:14:25

深度优先搜索（Depth-First Search，简称 DFS）是一种用于遍历或搜索树或图的算法。DFS 从根节点开始，尽可能深的搜索树的分支，当节点 v 的所在边都己被探寻过，搜索将回溯到上一个节点 w，然后探索 w 的其他未搜索过的子节点。DFS 有两种常用的方式：递归方式和非递归方式（通常使用栈来实现）。

深度优先搜索的基本步骤：

选择起点：选择一个顶点作为搜索的起点。
访问顶点：标记这个顶点为已访问，并对它进行必要的操作。
探索邻接点：选择一个未访问的邻接顶点，然后递归地执行 DFS。
回溯：当到达叶子节点或所有邻接顶点都已访问时，回溯到上一个调用。
重复：如果还有未访问的顶点，则选择其中一个作为新的起点，重复上述过程。

Java 中使用递归实现 DFS：

假设我们有一个邻接矩阵 graph 代表无向图，其中 graph[i][j] 为真表示节点 i 和 j 之间存在边。

import java.util.*;public class DFS {private boolean[] visited; // 标记每个顶点是否已被访问public DFS(int vertices) {visited = new boolean[vertices];}// 递归实现的 DFSpublic void dfsRecursion(int vertex) {visited[vertex] = true;System.out.print(vertex + " ");for (int i = 0; i < visited.length; i++) {if (graph[vertex][i] && !visited[i]) {dfsRecursion(i);}}}// 非递归实现的 DFS 使用栈public void dfsNonRecursion(int startVertex) {Stack<Integer> stack = new Stack<>();stack.push(startVertex);visited[startVertex] = true;while (!stack.isEmpty()) {int currentVertex = stack.pop();System.out.print(currentVertex + " ");for (int i = 0; i < visited.length; i++) {if (graph[currentVertex][i] && !visited[i]) {stack.push(i);visited[i] = true;}}}}public static void main(String[] args) {int vertices = 4; // 假设有4个顶点int[][] graph = {{0, 1, 0, 0},{1, 0, 1, 1},{0, 1, 0, 0},{0, 1, 0, 0}};DFS dfs = new DFS(vertices);dfs.dfsRecursion(0); // 从顶点0开始DFSSystem.out.println();Arrays.fill(dfs.visited, false); // 重置已访问标记dfs.dfsNonRecursion(0); // 从顶点0开始非递归DFS}
}

注意事项：

在遍历图时，需要确保不会无限循环，因此需要标记已经访问过的顶点。
当图中存在多个连通分量时，可能需要多次调用 DFS 来遍历整个图。
DFS 可以用于解决许多问题，包括但不限于拓扑排序、检测环、路径查找等。

以上是 DFS 在 Java 中的基本实现。你可以根据具体的图数据结构和问题需求进行相应的调整。

当然，我们可以对上面提供的深度优先搜索（DFS）代码进行一些调整和增强，使其更通用和健壮。以下是一些可能的改进：

参数化图结构：使用泛型来支持不同类型的图结构，例如邻接矩阵或邻接表。
处理图中的多个连通分量：遍历所有顶点，确保所有顶点都被访问，即使它们不在同一个连通分量中。
异常处理和边界检查：增加对输入的验证，如检查图是否为空，顶点索引是否有效等。
可读性和代码风格：改善代码的可读性，例如使用更具描述性的变量名和添加注释。

下面是使用邻接表实现的 DFS 示例，同时处理多个连通分量：

import java.util.*;public class GraphDFS<T> {private Map<T, List<T>> adjacencyList;private Set<T> visited;public GraphDFS() {this.adjacencyList = new HashMap<>();this.visited = new HashSet<>();}// 添加顶点public void addVertex(T vertex) {adjacencyList.putIfAbsent(vertex, new ArrayList<>());}// 添加边public void addEdge(T src, T dest) {if (!adjacencyList.containsKey(src) || !adjacencyList.containsKey(dest)) {throw new IllegalArgumentException("Vertex does not exist.");}adjacencyList.get(src).add(dest);// 如果是无向图，也需要反向添加adjacencyList.get(dest).add(src);}// 递归 DFSpublic void dfsRecursive(T vertex) {if (!adjacencyList.containsKey(vertex)) {throw new IllegalArgumentException("Vertex does not exist.");}visited.add(vertex);System.out.print(vertex + " ");for (T neighbor : adjacencyList.get(vertex)) {if (!visited.contains(neighbor)) {dfsRecursive(neighbor);}}}// 非递归 DFS 使用栈public void dfsIterative(T startVertex) {if (!adjacencyList.containsKey(startVertex)) {throw new IllegalArgumentException("Vertex does not exist.");}Stack<T> stack = new Stack<>();stack.push(startVertex);visited.add(startVertex);while (!stack.isEmpty()) {T currentVertex = stack.pop();System.out.print(currentVertex + " ");for (T neighbor : adjacencyList.get(currentVertex)) {if (!visited.contains(neighbor)) {stack.push(neighbor);visited.add(neighbor);}}}}// 遍历整个图public void dfs() {for (T vertex : adjacencyList.keySet()) {if (!visited.contains(vertex)) {dfsRecursive(vertex);}}visited.clear(); // 清除已访问标志，以便再次遍历时重新使用for (T vertex : adjacencyList.keySet()) {if (!visited.contains(vertex)) {dfsIterative(vertex);}}}public static void main(String[] args) {GraphDFS<String> graph = new GraphDFS<>();// 添加顶点graph.addVertex("A");graph.addVertex("B");graph.addVertex("C");graph.addVertex("D");// 添加边graph.addEdge("A", "B");graph.addEdge("B", "C");graph.addEdge("C", "D");graph.addEdge("D", "A");// 执行 DFSgraph.dfs();}
}

这个版本的代码提供了更广泛的适用性，可以处理任何类型（泛型 T）的顶点，并且可以处理无向图。同时，它确保了即使图由多个不相连的分量组成，DFS 也会遍历到所有的顶点。

为了使代码更加完善，我们可以添加一些额外的功能和改进，例如：

分离 DFS 方法：将 DFS 的递归和迭代方法分离成独立的类或方法，以便于测试和复用。
增加日志记录或调试信息：在关键步骤中添加日志输出，以便于调试和理解程序运行流程。
异常处理细化：提供更具体的异常信息，帮助用户理解问题所在。
性能优化：在迭代 DFS 中，优化邻接顶点的查找，避免重复检查是否已访问。

以下是基于上述改进的代码示例：

import java.util.*;public class Graph<T> {private final Map<T, List<T>> adjacencyList;private final Set<T> visited;public Graph() {this.adjacencyList = new HashMap<>();this.visited = new HashSet<>();}public void addVertex(T vertex) {adjacencyList.putIfAbsent(vertex, new ArrayList<>());}public void addEdge(T src, T dest) {if (!adjacencyList.containsKey(src) || !adjacencyList.containsKey(dest)) {throw new NoSuchElementException("One or both vertices do not exist.");}adjacencyList.get(src).add(dest);adjacencyList.get(dest).add(src); // 无向图}public void dfs() {for (T vertex : adjacencyList.keySet()) {if (!visited.contains(vertex)) {dfsRecursive(vertex);}}visited.clear();for (T vertex : adjacencyList.keySet()) {if (!visited.contains(vertex)) {dfsIterative(vertex);}}}private void dfsRecursive(T vertex) {if (!adjacencyList.containsKey(vertex)) {throw new NoSuchElementException("Vertex does not exist.");}visited.add(vertex);System.out.print(vertex + " ");for (T neighbor : adjacencyList.get(vertex)) {if (!visited.contains(neighbor)) {dfsRecursive(neighbor);}}}private void dfsIterative(T startVertex) {if (!adjacencyList.containsKey(startVertex)) {throw new NoSuchElementException("Vertex does not exist.");}Stack<T> stack = new Stack<>();stack.push(startVertex);visited.add(startVertex);while (!stack.isEmpty()) {T currentVertex = stack.pop();System.out.print(currentVertex + " ");List<T> neighbors = adjacencyList.get(currentVertex);for (int i = neighbors.size() - 1; i >= 0; i--) { // Reverse iteration to avoid re-checking visited flagT neighbor = neighbors.get(i);if (!visited.contains(neighbor)) {stack.push(neighbor);visited.add(neighbor);}}}}
}// Test code
public class Main {public static void main(String[] args) {Graph<String> graph = new Graph<>();// Adding verticesgraph.addVertex("A");graph.addVertex("B");graph.addVertex("C");graph.addVertex("D");graph.addVertex("E");// Adding edgesgraph.addEdge("A", "B");graph.addEdge("B", "C");graph.addEdge("C", "D");graph.addEdge("D", "A");graph.addEdge("E", "C"); // Separate component// Perform DFSgraph.dfs();}
}