深度优先搜索遍历 java

深度优先搜索（Depth First Search，简称DFS）是一种用于遍历或搜索树或图数据结构的算法。在Java中，我们可以使用递归或栈来实现深度优先搜索。以下是简单的深度优先搜索遍历步骤：

1. **选择一个起始节点**：通常从根节点开始，或者任意未访问过的节点。

2. **标记当前节点为已访问**：将其设置为已访问状态，防止重复访问。

3. **访问当前节点**：对当前节点执行所需的操作，如打印节点值。

4. **递归或循环展开**：对于当前节点的所有邻接节点，如果它们还未访问过，就进行下一步操作，即进入下一个邻接节点并重复上述过程。

5. **回溯**：当所有可达的节点都访问过后，返回上一层，继续处理其他分支，直到整个图或树都被访问完。

下面是一个基本的递归版DFS遍历Java代码示例（假设有一个无向图表示为邻接列表）：

import java.util.*;

public class DFS {
    private boolean[] visited; // 记录节点是否已访问

    public void dfs(int node, List<Integer>[] graph) {
        visited[node] = true;
        System.out.println(node); // 打印当前节点
        for (int neighbor : graph[node]) { // 遍历邻居
            if (!visited[neighbor]) {
                dfs(neighbor, graph);
            }
        }
    }

    public static void main(String[] args) {
        int[][] graph = {{1, 2}, {2, 3}, {3, 4}};
        DFS dfs = new DFS();
        visited = new boolean[5]; // 初始化所有节点未访问
        dfs.dfs(1, convertAdjListToArray(graph)); // 使用递归从1开始
    }

    private static List<Integer>[] convertAdjListToArray(int[][] graph) {
        int size = graph.length;
        List<Integer>[] adjList = new ArrayList[size];
        for (int i = 0; i < size; i++) {
            adjList[i] = new ArrayList<>();
            for (int j = 0; j < graph[i].length; j++) {
                if (graph[i][j] != -1) {
                    adjList[i].add(graph[i][j]);
                }
            }
        }
        return adjList;
    }
}