Java实现DFS遍历图时重复访问顶点问题排查求助

你的代码出现重复访问顶点的核心原因有两个：

1. 标记对象错误 #

你在Node类中定义的marked字段是每条边的终点实例标记，而非顶点本身的标记。比如顶点0在边(0,1)和(2,0)中对应两个不同的Node对象，标记其中一个不会影响另一个，导致当处理顶点2时，指向0的Node仍处于未标记状态，会再次将0压入栈。

2. 缺少顶点访问检查 #

从栈中弹出顶点后，你没有判断该顶点是否已经被处理（输出）过，导致同一个顶点被多次弹出并重复输出。

修改后的代码 #

class Graph{
    class Node{
        int vertex;
        int cost;
        
        Node (int vertex, int cost){
            this.vertex = vertex;
            this.cost = cost;
        }

        public int getVertex() {
            return this.vertex;
        }
    }
    
    List<ArrayList<Node>> adlist;
    int size;
    boolean[] visited; // 新增：记录每个顶点是否已访问
    
    Graph(int initsize){
        adlist = new ArrayList<ArrayList<Node>>();
        this.size = initsize;
        visited = new boolean[initsize]; // 初始化顶点访问数组
        for(int i = 0; i < initsize; i++) {
            this.adlist.add(new ArrayList<Node>());
            visited[i] = false; // 初始状态为未访问
        }
    }
    
    public void put(int start, int dest, int weight) {
        this.adlist.get(start).add(new Node(dest, weight));
    }
    
    public void dfs(int index) {
        Stack<Integer> stack = new Stack<>();
        stack.push(index);
        
        while(!stack.isEmpty()) {
            int r = stack.pop();
            
            if(visited[r]) { // 若顶点已访问，直接跳过
                continue;
            }
            
            visited[r] = true; // 标记顶点为已访问
            System.out.printf("%d ", r); // 输出当前顶点
            
            // 逆序遍历邻接列表，保证DFS遍历顺序与递归逻辑一致
            List<Node> neighbors = adlist.get(r);
            for(int i = neighbors.size() - 1; i >= 0; i--) {
                Node neighbor = neighbors.get(i);
                if(!visited[neighbor.getVertex()]) {
                    stack.push(neighbor.getVertex());
                }
            }
        }   
    }
}

关键修改说明 #

• 移除Node类的marked字段，改用Graph类的visited数组统一标记顶点访问状态，确保每个顶点只有一个全局标记。
• 弹出顶点后先检查visited[r]，避免重复处理已访问的顶点。
• 逆序遍历邻接列表并压入栈，保证弹出顺序与递归DFS的遍历顺序一致（比如你的示例中，0的邻接节点1、5会被逆序压入5、1，栈弹出时先处理5，符合你预期的输出0 5 1 4 2 3）。

内容的提问来源于stack exchange，提问作者Hyeonbinshin