java深度优先遍历

Java中的深度优先遍历（Depth-First Search，简称DFS）是一种用于图或树的遍历算法。下面是一个使用递归实现深度优先遍历的示例代码：

import java.util.ArrayList;
import java.util.List;

class Graph {
    private int vertices;
    private List<List<Integer>> adjList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination) {
        adjList.get(source).add(destination);    }

    private void dfsUtil(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");

        for (int neighbor : adjList.get(v)) {
            if (!visited[neighbor]) {
                dfsUtil(neighbor, visited);
            }
        }
    }

    public void DFS(int startVertex) {
        boolean[] visited = new boolean[vertices];
        dfsUtil(startVertex, visited);
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);

        System.out.println("Depth-First Traversal (starting from vertex 0):");
        graph.DFS(0);
    }
}

在上述代码中，我们首先定义了一个Graph类来表示图。构造函数中初始化了邻接表和顶点数。addEdge方法用于添加边。

在dfsUtil方法中，我们使用了递归来进行深度优先遍历。我们首先将当前顶点标记为已访问，并打印该顶点。然后递归遍历该顶点的所有未访问过的邻居。

最后，在main方法中创建一个Graph对象，并添加边。然后调用DFS方法来开始深度优先遍历。

输出结果为：0 1 3 4 2，表示从顶点0开始的深度优先遍历路径。

希望这个示例能够帮助你理解Java中的深度优先遍历。如有疑问，请随时提问。