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!
        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(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]");
        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] : "")));
    public static void main(String[] args) {
        Graph g = new Graph(6);
        g.addEdge(0, 2);
        g.addEdge(0, 1);
        g.addEdge(3, 5);
        g.addEdge(0, 5);
        g.addEdge(1, 2);
        g.addEdge(3, 4);
        g.addEdge(2, 3);
        g.addEdge(2, 4);
        DepthFirstPathFinder dfpf = new DepthFirstPathFinder2(g,0);