图最长路径求解问题：DFS递归实现返回结果异常求助

看起来你现在的DFS逻辑能遍历路径，但没做好最长路径的追踪和筛选，导致输出了所有路径而非你需要的那条最长的。咱们来调整下思路和代码，搞定这个问题：

核心问题分析 #

你当前的代码应该是在递归过程中直接输出了每一条遍历到的路径，但没有在递归时持续对比并保留长度最长的那条路径。所以咱们要做的就是在DFS的每一步都记录当前最优的路径，最后只返回这条最长的。

调整后的实现思路 #

1. 新增类级变量存储最长路径：用来持续追踪当前找到的最长路径，避免每次递归都输出所有路径
2. 优化DFS的回溯逻辑：
   • 进入递归先把当前城市加入路径
   • 对比当前路径长度和已记录的最长路径，更长就更新最长路径（注意要深拷贝，避免后续修改影响）
   • 遍历邻接城市时跳过已在路径中的城市（防止环，也避免重复走）
   • 递归结束后移除当前城市（回溯，保证其他分支路径的正确性）

修改后的代码示例 #

// 类级别变量，专门存当前找到的最长路径
private ArrayList<String> longestPath = new ArrayList<>();

// 对外暴露的方法，传入起始城市启动查找
public void getLongestPath(City startCity) {
    ArrayList<String> currentPath = new ArrayList<>();
    dfs(startCity, currentPath);
    // 最后输出目标最长路径
    System.out.println("最长路径：" + longestPath);
}

private void dfs(City currentCity, ArrayList<String> currentPath) {
    // 把当前城市加入当前路径
    currentPath.add(currentCity.getName());

    // 如果当前路径比已记录的最长路径更长，就更新最长路径
    if (currentPath.size() > longestPath.size()) {
        // 必须深拷贝，不然后续修改currentPath会同步改变longestPath
        longestPath = new ArrayList<>(currentPath);
    }

    // 遍历当前城市的所有邻接城市，跳过已经在路径里的（避免环）
    for (City neighbor : currentCity.getNeighbors()) {
        if (!currentPath.contains(neighbor.getName())) {
            dfs(neighbor, currentPath);
        }
    }

    // 回溯：移除当前城市，去探索其他分支路径
    currentPath.remove(currentPath.size() - 1);
}

关键细节提醒 #

• 回溯不能忘：递归返回后一定要移除当前城市，不然后续的路径分支会包含错误的城市节点
• 深拷贝路径：更新最长路径时必须新建ArrayList，不能直接赋值引用，否则后续修改当前路径会搞乱已保存的最长路径
• 防环处理：跳过已在当前路径中的邻接城市，避免无限循环和无效的环路径

把这段逻辑整合到你的代码里，再测试从拉斯维加斯出发的场景，应该就能得到你预期的[Las Vegas, Salt Lake City, Denver, Helena, Winnipeg, Duluth]这条最长路径了。

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