java实现深度优先搜索(DFS)算法

度优先搜索（Depth First Search，DFS）算法是一种用于遍历或搜索图或树的算法。这种算法从一个节点开始，沿着一条路径尽可能深地搜索，直到遇到不能继续前进的节点时返回上一个节点，然后继续搜索其他路径。具体步骤如下：

选择一个起始节点作为当前节点，并将其标记为已访问。尝试从当前节点出发，依次访问其未访问的邻接节点。对于每个邻接节点，如果它未被访问过，则将其设为当前节点，并进行深度优先搜索。如果当前节点没有未访问的邻接节点，返回上一个节点，将其设为当前节点，并继续搜索其他路径。重复步骤2-4，直到所有节点都被访问。

深度优先搜索算法通常使用递归实现，因为它能够自然地利用函数调用栈来保存当前节点的状态。在实际应用中，深度优先搜索算法可以用来解决迷宫问题、拓扑排序、连通性判断等问题。

以下是Java实现深度优先搜索（DFS）算法的示例代码：

import java.util.ArrayList; import java.util.List; import java.util.Stack; class Graph { private int V; // 顶点数量 private List<List<Integer>> adj; // 邻接表 public Graph(int V) { this.V = V; adj = new ArrayList<>(V); for (int i = 0; i < V; ++i) adj.add(new ArrayList<>()); } // 添加边 public void addEdge(int v, int w) { adj.get(v).add(w); } // 递归实现DFS private void DFSUtil(int v, boolean[] visited) { visited[v] = true; System.out.print(v + " "); for (int i : adj.get(v)) { if (!visited[i]) DFSUtil(i, visited); } } // DFS遍历 public void DFS(int v) { boolean[] visited = new boolean[V]; DFSUtil(v, visited); } // 迭代实现DFS public void DFSIterative(int v) { boolean[] visited = new boolean[V]; Stack<Integer> stack = new Stack<>(); stack.push(v); while (!stack.isEmpty()) { v = stack.pop(); if (!visited[v]) { visited[v] = true; System.out.print(v + " "); for (int i : adj.get(v)) { if (!visited[i]) { stack.push(i); } } } } } } public class Main { public static void main(String[] args) { Graph graph = new Graph(6); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(2, 4); graph.addEdge(2, 5); System.out.println("DFS recursive:"); graph.DFS(0); System.out.println("\nDFS iterative:"); graph.DFSIterative(0); } }

本示例中，我们首先创建了一个Graph类表示图。构造函数中，我们初始化了邻接表adj，并定义了边的连接关系。

然后，我们实现了递归和迭代版本的DFS。递归版本的DFS使用了一个辅助函数DFSUtil来进行递归的深度优先搜索。迭代版本的DFS使用了一个Stack来保存待访问的顶点。

在Main函数中，我们创建了一个具有6个顶点的图，并添加了几条边。接着，我们分别调用了递归和迭代版本的DFS来进行深度优先搜索。