找出图中最长的路径

Question

我试图在图中找到最长的路径，但在返回最长路径时遇到了问题。我已经弄清楚了递归并且可以跟随输出但是我无法获得正确的输出。该程序目前有 returns 条路径。

从拉斯维加斯出发时的预期输出：[拉斯维加斯、盐湖城、丹佛、海伦娜、温尼伯、德卢斯]

我的深度优先搜索方法：

public void dfs(City before, ArrayList<String> listOfCities){

    System.out.println(before +"-->"+ before.getAdjCities());

    List<City> neighbours = before.getAdjCities();
    before.setVisited(true);

    for (int i = 0; i < neighbours.size(); i++) {

        City n = neighbours.get(i);
        if(!n.visited){
            listOfCities.add(n.getCityName());
            System.out.println(i+ " Test: " + listOfCities.toString());

            dfs(n, listOfCities);
        }
    }
}

这是输出：

这是图表：

Answer 1

您的 ListOfCities 在搜索的所有分支中都是静态的，这就是它最终包含所有城市的原因。每个城市的递归步骤应该比较每个邻居的 DFS 结果来构建结果。

找出图中最长的路径

Find the longest path in graph

java

depth-first-search