DFS迷宫寻路算法重复访问节点致栈溢出问题求助

1. 未标记已访问节点（最常见） #

DFS遍历的核心就是要避免重复访问节点，不然会在相邻节点间无限循环（比如节点A→节点B→节点A→节点B……），最终把栈撑爆触发溢出。你的代码大概率没维护一个已访问集合（比如Set<Node>），也没给Node类加isVisited布尔属性，每次递归或栈遍历的时候没检查节点是否已经访问过，导致反复钻进同一个节点。

2. 已访问标记的时机不对 #

如果已经加了标记，但时机错了也会出问题：

• 比如在回溯时错误清除了标记：如果是找所有路径，回溯时清标记是对的，但如果只是找单一路径，清标记会让节点被后续遍历再次访问；
• 或者进入节点后没立即标记，等处理完所有邻居才标记，这会导致同一个节点被多个邻居的递归调用重复进入。

3. 节点的相等性判断错误 #

如果你的Node类没正确重写equals()和hashCode()方法，用Set<Node>存已访问节点时，会把坐标相同的不同Node对象当成不同节点，根本拦不住重复访问。

4. 递归终止条件不严谨 #

比如没正确判断当前节点是不是终点，或者找到终点后没立即终止递归，还继续遍历其他路径，叠加重复访问的问题，更快触发栈溢出。

举个简单的正确标记示例（Java）：

class Node {
    int x, y;
    boolean isVisited;
    // 构造方法、getter等
}

// DFS核心方法
private boolean dfs(Node current, Node end) {
    // 找到终点直接返回
    if (current.x == end.x && current.y == end.y) {
        return true;
    }
    // 进入节点后立即标记已访问
    current.isVisited = true;
    // 遍历上下左右邻居节点
    for (Node neighbor : getNeighbors(current)) {
        // 只处理未访问且可通行的节点
        if (!neighbor.isVisited && neighbor.isWalkable()) {
            if (dfs(neighbor, end)) {
                return true; // 找到路径后直接终止递归
            }
        }
    }
    // 仅当需要找所有路径时才清除标记，单一路径不需要这行
    // current.isVisited = false;
    return false;
}

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