# 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:

```/**
* represents a path of connected vertices and edges in the graph
*/
public class DGPath {
private V start = null;
private double totalWeight = 0.0;
private Set<V> visited = new HashSet<>();

/**
* representation invariants:
* 1. The edges are connected by vertices, i.e. FOR ALL i: 0 < i < edges.length: edges[i].from == edges[i-1].to
* 2. The path begins at vertex == start
* 3. if edges is empty, the path also ends at vertex == start
* otherwise edges.from == start and the path continues along edges[i].to for all 0 <= i < edges.length
**/

@Override
public String toString() {
StringBuilder sb = new StringBuilder(
String.format("Weight=%f Length=%d Visited=%d (",
this.totalWeight, 1 + this.edges.size(), this.visited.size()));
sb.append(start.getId());
for (E e : edges) {
sb.append(", " + e.getTo().getId());
}
sb.append(")");
return sb.toString();
}

public V getStart() {
return start;
}

return edges;
}

public double getTotalWeight() {
}

public Set<V> getVisited() {
return visited;
}
}
```

Below the `Depth first search method`:

```/**
* Uses a depth-first search algorithm to find a path from the start vertex to the target vertex in the graph
* The path.totalWeight should indicate the number of edges in the result path
* All vertices that are being visited by the search should also be registered in path.visited
*
* @param startId the id of the start Vertex
* @param targetId the id of the end Vertex
* @return the DGpath for the path from start to target
* returns null if either start or target cannot be matched with a vertex in the graph
* or no path can be found from start to target
*/
public DGPath depthFirstSearch(String startId, String targetId) {

V start = this.getVertexById(startId);
V target = this.getVertexById(targetId);
if (start == null || target == null) return null;

DGPath path = new DGPath();
path.start = start;

// easy target
if (start == target) return path;

// TODO calculate the path from start to target by recursive depth-first-search
//  (create another private recursive helper method)
//  register all visited vertices while going, for statistical purposes
//  if you hit the target: complete the path and bail out !!!

for (E edge : start.getEdges()) {
if (!path.getVisited().contains(target)) {
dfsHelper(edge.getTo(), path.visited);
} else {
return path;
}
}

// no path found, graph was not connected ???
return null;
}
```

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

```private void dfsHelper(V current, Set<V> discovered) {
for (E edge : current.getEdges()) {
while(edge.getTo() != null){
V nextV = edge.getTo();
if (!discovered.contains(nextV)) {
dfsHelper(nextV, discovered);
}
}
}

}
```

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`?

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 `