CODEWITHSUNDEEP
javadepth-first-search
user5553106
user5553106

Reputation:

Find the longest path in graph

I am trying to find the longest path in a graph but I'm having trouble when it comes to returning the longest path. I have the recursion figured out and can follow the outputs but I can't get the right output. The program currently returns several paths.

The expected output is when starting from Las Vegas: [Las Vegas, Salt Lake City, Denver, Helena, Winnipeg, Duluth]

My depth first search method:

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);
        }
    }
}

Here is the output:

enter image description here

Here is the graph:

enter image description here

Upvotes: 2

Views: 1065

Answers (1)

Steve B
Steve B

Reputation: 88

Your ListOfCities is static across all branches of your search, which is why it ends up with all the cities. The recursive step at each city should compare the result of the DFS from each neighbor to build the result.

Upvotes: 1

Related Questions