# Depth-First Pathfinder (Recursive)

The following class conducts a recursive depth-first search of a given graph with a given "root" $s$, in its constructor so that it can answer questions like "Are vertices $v$ and $s$ connected?", "What path should be followed to travel from the $s$ to a given vertex v?":


import java.util.Iterator;

public class DepthFirstPathFinder {  // Recursive version

// the following vertex serves as the "root" of our depth-first
// search tree.  all paths found lead back to s
private final int s;

// the following array gives the parent vertex to the index vertex
// based on the depth first search.  So if edgeTo[w] == v
// then edge v-w was taken to visit w the first time.
// further, when edgeTo[w] != NOT_FOUND, it has been visited
private int[] edgeTo;

// keeps track of whether a vertex has been visited by the dfs yet (all initially false)
private boolean[] marked;

// constructor that establishes the starting "root" for the dfs, vertex s
public DepthFirstPathFinder(Graph g, int s) {
marked = new boolean[g.numVertices()];  // build marked array
edgeTo = new int[g.numVertices()];      // build edgeTo array

this.s = s;  // set the instance variable s to keep track of the "root" for the dfs

dfs(g,s);  // do the depth-first search now, at construction time
// so you only have to do it once, and store the tree
// structure found in edgeTo[] and the vertices of the
// connected component containing s, along the way. This
// makes the other methods of this class quick to execute
// at later times.
}

// recursive depth-first search, building paths to vertex s
// along the way
private void dfs(Graph g, int v) {

marked[v] = true;  // we just visited vertex v!
printStateSoFar(g);

for (int w : g.adj(v)) {

if ( ! marked[w] ) {  // i.e., if we haven't already visited w...
edgeTo[w] = v;    // set parent link for v for dfs tree
dfs(g, w);
}
}
}

public boolean hasPathTo(int v) {
return marked[v];  // if we visited it from root, there must be a path...
}

public Iterable<Integer> pathTo(int v) {
if (! hasPathTo(v))
return null;

// since edgeTo[w] gives the parent of w, we
// use a stack to reverse/store the path vertices
Stack<Integer> path = new Stack<Integer>();
for (int w = v; v != s; w = edgeTo[w])
path.push(w);
path.push(s);  // don't forget to push the root (it has no parent in edgeTo[])
return path;
}

// this is a method that lets us see the states marked[]
// and edgeTo[] arrays
private void printStateSoFar(Graph g) {
System.out.println(" i | edgeTo[i]");
System.out.println("---|----------");
for (int i = 0; i < g.numVertices(); i++)
// print "-" if i is root, print parent (edgeTo[i]) if marked, and print nothing otherwise
System.out.println(" " + i + " |    " + ((i == s) ? "-" : (marked[i] ? edgeTo[i] : "")));
System.out.println();
System.out.println();
}

public static void main(String[] args) {
Graph g = new Graph(6);