深度优先搜索（DFS）在有向图中的正确实现（Java）-java教程-PHP中文网

深度优先搜索（dfs）在有向图中的正确实现（java）

本文详解如何在基于邻接表（ArrayList）的有向图中正确实现深度优先遍历，重点纠正常见误区——未检查顶点是否已访问即盲目入栈导致无限循环或遗漏节点的问题，并提供可运行、带状态管理的完整代码示例。

本文详解如何在基于邻接表（ArrayList>）的有向图中正确实现深度优先遍历，重点纠正常见误区——未检查顶点是否已访问即盲目入栈导致无限循环或遗漏节点的问题，并提供可运行、带状态管理的完整代码示例。

在有向图的深度优先搜索（DFS）中，核心逻辑是递归回溯或显式栈驱动的“探索—标记—跳过已访问”流程。原代码虽使用了栈结构，但存在两个致命缺陷：

未校验 wasVisited 状态就强制将邻接顶点入栈并设为 true，导致重复访问与死循环；
错误地耦合了图索引（graphCounter）与当前处理顶点的逻辑，使遍历路径完全依赖线性扫描，丧失图结构语义。

正确的 DFS 实现应以当前顶点为起点，遍历其所有邻接顶点，仅对未访问者压栈。以下是重构后的专业级实现：

JavaStoryDevelop

你接手一个需求时，是不是经常这样："改一个小字段 → 结果把不相关的代码也改了"、"需求说得很模糊 → 做着做着发现跑偏了"、"数据库加个字段 → 上线才发现漏了数据兼容"、"做了个新功能 → 一个月后自己都忘了当时怎么设计的"、"写到一半被中断 → 再回来不知道从哪继续"；这个 Skill 就是专门解决这些问题的。它会自动探测你的项目环境（JDK、Spring Boot、ORM、数据库、前端框架），记在

下载

✅ 正确实现要点

每个 Vertex 必须包含 data（标识符）和 wasVisited（布尔状态）字段；
邻接表 graph 的索引应与顶点 data 一一对应（如 graph.get(0) 存储顶点 "0" 的出边），或通过哈希映射快速定位；
关键守卫条件：if (!next.wasVisited) —— 这是避免重复/死循环的唯一防线。

✅ 完整可运行代码（含 Vertex 类与测试用例）

import java.util.*;

class Vertex {
    String data;
    boolean wasVisited;

    Vertex(String data) {
        this.data = data;
        this.wasVisited = false;
    }
}

class DirectedGraph {
    private final List<list>> graph; // 推荐使用 List<list>> 替代 ArrayList<linkedlist>>

    public DirectedGraph(int n) {
        this.graph = new ArrayList(n);
        for (int i = 0; i ());
        }
    }

    // 添加有向边 u → v
    public void addEdge(String u, String v) {
        int uIdx = Integer.parseInt(u);
        int vIdx = Integer.parseInt(v);
        if (uIdx  stack = new Stack();
        stack.push(start);
        start.wasVisited = true;

        while (!stack.isEmpty()) {
            Vertex current = stack.pop();
            System.out.print(current.data + " ");

            // 遍历 current 的所有直接后继（邻接顶点）
            int currentIdx = Integer.parseInt(current.data);
            for (Vertex neighbor : graph.get(currentIdx)) {
                if (!neighbor.wasVisited) { // ✅ 核心检查：仅未访问顶点入栈
                    neighbor.wasVisited = true;
                    stack.push(neighbor);
                }
            }
        }
        System.out.println();
    }

    // 重载：支持从编号启动（如 dfs(0)）
    public void dfs(int startIdx) {
        if (startIdx <h3>? 测试用例（复现题目期望输出 <code>0 2 4 5 1 3</code>）</h3>
<pre class="brush:php;toolbar:false;">public class DFSTest {
    public static void main(String[] args) {
        DirectedGraph g = new DirectedGraph(6); // 6 个顶点：0~5

        // 构建题目隐含图结构（依据期望输出反推常见拓扑）
        // 示例：0→2, 2→4, 4→5, 5→1, 1→3 —— 形成链式，但需确保 3 无出边且不被跳过
        g.addEdge("0", "2");
        g.addEdge("2", "4");
        g.addEdge("4", "5");
        g.addEdge("5", "1");
        g.addEdge("1", "3");

        // 启动 DFS（从顶点 "0" 开始）
        g.dfs(new Vertex("0")); // 输出：0 2 4 5 1 3 ✅
    }
}

⚠️ 注意事项与最佳实践

状态初始化：务必在调用 dfs() 前确保所有顶点 wasVisited = false，或在方法内统一重置；
索引健壮性：生产环境建议用 Map<string list>></string> 替代数组索引，避免 parseInt 强制转换风险；
栈 vs 递归：本例用栈实现（迭代版 DFS），若改用递归，逻辑更直观（visit(v); for (w : adj[v]) if (!w.visited) dfs(w);），但需注意栈溢出；
时间复杂度：O(V + E)，其中 V 为顶点数，E 为边数；空间复杂度 O(V)（栈+访问标记）。