# Breadth First Path Finder

The following class conducts a breadth-first search of a given graph with a given "source" $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 using the smallest number of edges?":

import java.util.Iterator;

public class BreadthFirstPathFinder {  // Recursive version

// the following vertex serves as the "source node" of our breadth-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 breadth first search.  So if edgeTo[w] == v
// then edge v-w was taken to visit w the first time.
private int[] edgeTo;

// the array below tracks if a vertex has been visited yet (all initially false)
private boolean[] marked;

// constructor that establishes the starting "source node" for the bfs, vertex s
public BreadthFirstPathFinder(Graph g, int s) {

marked = new boolean[g.numVertices()];  // build marked array
edgeTo = new int[g.numVertices()];      // build edgeTo array

this.s = s;
bfs(g,s);  // do the breadth-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 breadth-first search, building paths to vertex s
// along the way
private void bfs(Graph g, int s) {
Queue<Integer> q = new Queue<Integer>();
q.enqueue(s);
marked[s] = true;
printStateSoFar(g,q);
while (! q.isEmpty()) {
int v = q.dequeue();
for (int w : g.adj(v)) {
if (! marked[w]) {
q.enqueue(w);
marked[w] = true;
edgeTo[w] = v;
}
}
printStateSoFar(g,q);
}
}

public boolean hasPathTo(int v) {
return marked[v];
}

public Iterable<Integer> shortestPathTo(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; w != s; w = edgeTo[w]) {
path.push(w);
}
return path;
}

// this is a method that lets us see the states of the queue,
// and the marked[] and edgeTo[] arrays
private void printStateSoFar(Graph g, Queue q) {
Iterator qIterator = q.iterator();
System.out.println("queue  edgeTo[]");

for (int i = 0; i < g.numVertices(); i++) {
System.out.println( " |" + (qIterator.hasNext() ? qIterator.next() : " ") +
"|     " + i + "|" +
((i == s) ? "-" : (marked[i] ? edgeTo[i] : "")));
}
System.out.println();
}

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

for (int i = 0; i < g.numVertices(); i++) {
System.out.print("shortest path between 0 and " + i +
" : ");
if (bfpf.hasPathTo(i)) {
System.out.print("" + 0 + " ");
for (int v : bfpf.shortestPathTo(i)) {
System.out.print(v + " ");
}
System.out.println();
}
else {
System.out.println("none");
}
}
}
}