page 12

Code for Graph BFS
//time: O(V + E), space: O(V + E)
import java.util.*;
public class BreadthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    int s;
    public BreadthFirstPaths(Graph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        bfs(G, s);
    }
    private void bfs(Graph G, int s) {
        Queue<Integer> queue = new LinkedList<>();
        marked[s] = true;
        queue.add(s);
        while(!queue.isEmpty()) {
            int v = queue.poll();
            for(int w : G.adj(v)) {
                if(!marked[w]) {
                    marked[w] = true;
                    edgeTo[w] = v;
                    queue.add(w);
                }
            }
        }
    }
    public boolean hasPathTo(v) {return marked[v];}
    public Iterator<Integer> pathTo(int v) {
        if(!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<>();
        for(int x = v; x != s; x = edgeTo[x]) path.push(x);
        path.push(s);
        return path;
    }
}