Skip to content
Advertisement

Add edges of the path to list on Depth first Search Java

Im trying to implement depth first search algorithm on a directed graph. The graph exists of Vertices (V Vertex), each Vertex has a set of edges (E Edge). Each edge has a pointer to the next (.getTo()) and a pointer to the previous (.getFrom()). I want to find the path of edges from a start Vertex to a Target Vertex. To store and create a path I have created a helper class DGPath. I want to do this in a recursive way.

Below the DGPath create path helper class:

JavaScript

Below the Depth first search method:

JavaScript

And final, below the recursive helper method for the depth first search method:

JavaScript

This code does not work right now, it keeps stuck in the recursion.

  • How can I change this code to find the right path from start Vertex to target Vertex?
  • How can I save the edges that are used to get from start to target in DGPath.edges?

Advertisement

Answer

I think the problem is you call the dfsHelper function inside a for loop (which I see no reason why you need a loop!!). For each iteration you have to empty the path.visited at the end of loop, and again do path.visited.add(start);

Regarding your second question, define another field for path, say edges, and whenever you add a new node to path.visited, add the corresponding edge to path.edges (don’t forget to refresh the path.edges like path.visited for each iteration) the path.visited would have what you want after calling depthFirstSearch

User contributions licensed under: CC BY-SA
1 People found this is helpful
Advertisement