private boolean[] marked;
private int[] edgeTo[];
private 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> q = new LinkedList<>();
marked[s] = true;
q.add(s);
while(!q.isEmpty()) {
int v = q.poll();
for(int w : G.adj(v)) {
if(!marked[w]) {
marked[w] = true;
edgeTo[w] = v;
//what is missing here?
}
}
}
}
public boolean hasPathTo(int 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;
}
}