Java实现基于ArrayList<LinkedList>的有向图DFS遍历异常求助

我用ArrayList<LinkedList<Vertex>>结构实现有向图深度优先遍历（DFS）时遇到问题。正确遍历序列应为：0 2 4 5 1 3，但我的遍历结果只有0 2 4 5 1，调整代码又会陷入无限循环。

补充说明：顶点/节点的数据类型为字符串（示例用整数演示）。

原问题代码 #

ArrayList<LinkedList<Vertex>> graph;
    Vertex vertex;

    public DirectedGraph() {
        graph = new ArrayList<>();
        
    }

    public void dfSearch(Vertex vertex) {
        Stack<Vertex> stack = new Stack<>();
        String stringVal = null;
        int positionNum; // linkedlist position
        int graphCounter = 0; // arraylist position

        stack.push(vertex); 
        vertex.wasVisited = true;   

        while (!stack.isEmpty()) {
            Vertex a = stack.pop();
            System.out.println(a.data);
                        
                        // iterates through linkedlist and pushes into stack
            positionNum = 1;
            while (positionNum < graph.get(graphCounter).size()) { 
                Vertex next = graph.get(graphCounter).get(positionNum);
                next.wasVisited = true;
                stack.push(next);
                positionNum = positionNum + 1;
            } 
                        
                       // retrieves and stores Vertex/Node data
            stringVal = graph.get(graphCounter).get(positionNum-1).data; 
    
            // search for stringVal data within arraylist(graph)
            int i = 0;
            String search = graph.get(i).get(0).data;
            while ( search  != stringVal)  {
                i = i + 1;              
                search = graph.get(i).get(0).data;
            }
                        // once stringVal is found, its linkedlist position is stored
            graphCounter = i;
        }
    }


    public void dfs(int start) {
        dfSearch(graph.get(0).get(0));
    }

问题分析 #

你的代码存在3个核心逻辑错误：

1. 邻接表切换逻辑错误：graphCounter始终基于上一次的邻接表尾节点更新，而非当前弹出节点对应的邻接表，导致无法访问节点1的邻接节点3。
2. 提前标记已访问：入栈时直接标记所有邻接节点为已访问，会阻断后续合法路径的访问，甚至引发循环。
3. 起始节点无效：dfs方法的start参数未被使用，固定从第一个节点开始遍历，不符合方法设计预期。

修复后的代码 #

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

class Vertex {
    String data;
    boolean wasVisited;

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

public class DirectedGraph {
    ArrayList<LinkedList<Vertex>> graph;

    public DirectedGraph() {
        graph = new ArrayList<>();
    }

    // 根据节点数据找到其在graph中的邻接表索引
    private int findVertexIndex(Vertex target) {
        for (int i = 0; i < graph.size(); i++) {
            if (graph.get(i).get(0).data.equals(target.data)) {
                return i;
            }
        }
        return -1;
    }

    public void dfSearch(Vertex startVertex) {
        Stack<Vertex> stack = new Stack<>();
        stack.push(startVertex);
        startVertex.wasVisited = true;

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

            // 获取当前节点对应的邻接表
            int currentIndex = findVertexIndex(current);
            if (currentIndex == -1) continue;

            // 逆序压入邻接节点，保证DFS遍历顺序符合预期（栈后进先出特性）
            LinkedList<Vertex> adjList = graph.get(currentIndex);
            for (int i = adjList.size() - 1; i > 0; i--) {
                Vertex neighbor = adjList.get(i);
                if (!neighbor.wasVisited) {
                    neighbor.wasVisited = true;
                    stack.push(neighbor);
                }
            }
        }
    }

    public void dfs(int start) {
        // 重置所有节点的访问状态，避免多次调用时状态残留
        for (LinkedList<Vertex> list : graph) {
            for (Vertex v : list) {
                v.wasVisited = false;
            }
        }
        dfSearch(graph.get(start).get(0));
    }
}

修复要点 #

• 新增findVertexIndex方法，确保每次处理当前弹出节点的邻接表，解决节点遗漏问题。
• 仅标记未访问的邻接节点并入栈，避免提前标记导致的路径阻断。
• 逆序遍历邻接表压入栈，利用栈的后进先出特性保证DFS遍历顺序与预期一致。
• 修复dfs方法的起始节点逻辑，添加访问状态重置，支持多次调用。

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