递归实现有向图两点全路径DFS算法仅找到半数路径问题求助

核心问题点 #

• 字符串比较错误：终止条件中使用==比较字符串内容，Java中==仅对比对象引用，会导致大量实际匹配到目标节点的情况被漏判，直接少统计路径。
• 回溯未撤销边访问标记：仅在遍历边前设置了edge.setVisited(true)，但递归返回后没有将边的访问状态重置为false，导致同一条边全局仅能被使用一次，是路径只查出半数的核心原因。
• 变量/语法错误：
  • 方法参数是currPath，代码中混用curPath拼写，会直接抛出编译错误或运行时变量未定义异常
  • current参数声明为String类型，却调用了getAdjacent()方法，类型不匹配，实际应为Vertex类型
  • setVisited、removeLast均为方法调用，缺少括号，属于语法错误
  • for循环内重复定义edge变量，和外层声明冲突
• 无效的全局标记清除：代码末尾edge.clearVisited()调用的是外层未初始化的空edge对象，会触发空指针异常，且该逻辑完全不符合回溯要求，你需要的是每次递归返回后重置当前遍历边的标记，而非全局清除。

修正后的核心逻辑示例 #

private void findPaths(Vertex current, Vertex target, LinkedList<String> currPath) {
    // 匹配到目标节点，输出路径
    if(current.getNodeId().equals(target.getNodeId())) {
        System.out.println(currPath.toString());
        return;
    }
    // 遍历当前节点所有邻接节点
    for (Vertex neighbor : current.getAdjacent()) {
        Edge edge = getEdge(current.getNodeId() + neighbor.getNodeId());
        if(!edge.getVisited()) {
            // 标记边已访问，加入当前路径
            edge.setVisited(true);
            currPath.insertLast(neighbor.getNodeId());
            // 递归查找
            findPaths(neighbor, target, currPath);
            // 回溯：移除路径节点，撤销边访问标记
            currPath.removeLast();
            edge.setVisited(false);
        }
    }
}

补充说明 #

• 如果需求是查找简单路径（节点不重复），建议替换边访问标记为节点访问标记，避免同一节点多次进入形成环导致死循环
• 初始调用方法时，需要先将起点节点ID加入currPath中，否则输出的路径会缺失起点

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