Java 递归方法实现深度优先搜索（DFS）算法

一、项目背景详细介绍

深度优先搜索（Depth-First Search，DFS）是图论与树结构遍历中的经典算法，广泛应用于路径搜索、连通性检测、拓扑排序辅助、迷宫求解、回溯算法等场景。在实际工程中，我们经常需要：

• 网站爬虫：递归抓取页面链接；

• 连通分量标记：识别社交网络或网络拓扑中的子网；

• 路径可达性检测：判断任务依赖链是否完整；

• 拓扑排序：在DAG上进行逆后序遍历；

• 回溯搜索：数独、八皇后等组合问题的基础。

递归实现的 DFS 简洁自然，但需注意栈深度和可扩展性。本项目将基于 Java，使用邻接表存储图，完整实现并演示递归 DFS，包括：连通分量统计、路径可达性测试与遍历顺序记录。

---

二、项目需求详细介绍

1. 输入格式：

   • 从控制台读取图类型（0-无向图、1-有向图）、顶点数 n、边数 m；

   • 读取 m 条边 u v；若有向则 u->v，无向则双向。

2. 功能实现：

   • 构建邻接表 List<List<Integer>> adj；

   • 递归 dfs(int u, List<Integer> order) 方法：标记访问并遍历邻居；

   • countComponents()：统计并打印每个连通分量；

   • hasPath(int s, int t)：判断 s 到 t 可达性；

   • getDFSOrder(int start)：获取从指定起点的访问顺序。

3. 输出要求：

   • 打印连通分量列表及总数；

   • 打印可达性结果；

   • 打印 DFS 访问序列。

4. 性能与规模：

   • 支持 n,m 可达 10^5；

   • 递归栈深度可能接近 n，可通过 JVM 参数调整或改用显式栈。

5. 可扩展性：

   • GraphDFS 类封装，代码注释详尽；

   • 易于集成到其他项目或教学示例。

---

三、相关技术详细介绍

1. 邻接表存储：

   • 使用 List<List<Integer>> adj，空间复杂度 O(n + m)；

2. 递归 DFS：

   • 维护 boolean[] visited；

   • 递归调用处理回退与路径记录；

3. 连通分量统计：

   • 对每个未访问节点调用 DFS，形成一个分量；

4. 可达性检测：

   • 使用 visited 数组记录 DFS 结果；

5. 访问顺序记录：

   • 通过额外 order 列表收集访问顺序。

---

四、实现思路详细介绍

1. 构建图：

   List<List<Integer>> adj = new ArrayList<>(n);
   for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
   // 读取边 u, v
   adj.get(u).add(v);
   if (!directed) adj.get(v).add(u);
   

2. 递归 DFS：

   private void dfs(int u, List<Integer> order) {
       visited[u] = true;
       order.add(u);
       for (int v : adj.get(u)) {
           if (!visited[v]) dfs(v, order);
       }
   }
   

3. 连通分量：

   Arrays.fill(visited, false);
   int count = 0;
   for (int i = 0; i < n; i++) {
       if (!visited[i]) {
           List<Integer> comp = new ArrayList<>();
           dfs(i, comp);
           print comp; count++;
       }
   }
   

4. 路径可达性：

   Arrays.fill(visited, false);
   dfs(s, new ArrayList<>());
   return visited[t];
   

5. 访问顺序：

   List<Integer> order = new ArrayList<>();
   dfs(start, order);
   

---

五、完整实现源码

import java.util.*;

public class GraphDFS {
    private int n;
    private boolean directed;
    private List<List<Integer>> adj;
    private boolean[] visited;

    public GraphDFS(int n, boolean directed) {
        this.n = n;
        this.directed = directed;
        adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        visited = new boolean[n];
    }

    public void addEdge(int u, int v) {
        adj.get(u).add(v);
        if (!directed) adj.get(v).add(u);
    }

    // 递归 DFS
    private void dfs(int u, List<Integer> order) {
        visited[u] = true;
        order.add(u);
        for (int v : adj.get(u)) {
            if (!visited[v]) dfs(v, order);
        }
    }

    // 统计并打印连通分量
    public void countComponents() {
        Arrays.fill(visited, false);
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                List<Integer> comp = new ArrayList<>();
                dfs(i, comp);
                System.out.println("Component " + (++count) + ": " + comp);
            }
        }
        System.out.println("Total components = " + count);
    }

    // 检测 s 到 t 可达性
    public boolean hasPath(int s, int t) {
        Arrays.fill(visited, false);
        dfs(s, new ArrayList<>());
        return visited[t];
    }

    // 获取从 start 起的 DFS 访问顺序
    public List<Integer> getDFSOrder(int start) {
        Arrays.fill(visited, false);
        List<Integer> order = new ArrayList<>();
        dfs(start, order);
        return order;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入 n m directed(0无向 1有向)：");
        int n = sc.nextInt(), m = sc.nextInt(), dir = sc.nextInt();
        GraphDFS g = new GraphDFS(n, dir==1);
        System.out.println("输入 m 条边 u v：");
        for (int i = 0; i < m; i++) g.addEdge(sc.nextInt(), sc.nextInt());

        System.out.println("--- 连通分量 ---");
        g.countComponents();

        System.out.println("--- 可达性测试 ---");
        System.out.println("输入 s t：");
        int s = sc.nextInt(), t = sc.nextInt();
        System.out.println("Path exists: " + g.hasPath(s, t));

        System.out.println("--- DFS 访问顺序 ---");
        System.out.println(g.getDFSOrder(s));
    }
}

---

六、代码详细解读（只说明方法作用）

• dfs 方法：

  • 对顶点 u 进行递归访问并记录顺序；

• countComponents 方法：

  • 遍历所有顶点统计并打印连通分量；

• hasPath 方法：

  • 判断从 s 到 t 的可达性；

• getDFSOrder 方法：

  • 返回从指定起点的访问序列；

• main 方法：

  • 读取输入并执行以上功能；

---

七、项目详细总结

本项目以 Java 递归方式实现 DFS 算法，并演示了：

1. 连通分量统计；

2. 路径可达性检测；

3. 访问顺序记录；

算法时间复杂度 O(n + m)，空间复杂度 O(n + m)。

---

八、常见问题及解答

1. Q：递归栈深度过大怎么办？

   • A：可增加 JVM 栈大小参数或改为显式栈实现；

2. Q：无向图中如何避免重复访问？

   • A：visited 标记确保每个顶点仅访问一次；

3. Q：图中存在自环或平行边？

   • A：自环无影响，平行边会额外调用 DFS，但仍正确；

4. Q：如何扩展到加权图？

   • A：DFS 不保证最短路径，需结合 Dijkstra 或 BFS。

---

九、扩展方向与性能优化

1. 显式栈版本：避免递归深度过大；

2. 并行 DFS：分块图并行遍历；

3. 迭代器接口：将 DFS 封装为可重用迭代器；

4. 可视化演示：使用 JavaFX 动态绘制遍历过程；

5. 应用集成：将 GraphDFS 类打包为库供其他模块调用。

---