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 LinkedList<E> edges = new LinkedList<>();
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[0].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;
}
public LinkedList<E> getEdges() {
return edges;
}
public double getTotalWeight() {
return totalWeight;
}
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;
path.visited.add(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) {
discovered.add(current);
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
?
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