package Graph;
import java.util.*;
public class DirectedBFS {
private boolean[] visited;
private int[] pathTo;
private int[] distTo;
// private int start;
public DirectedBFS(DirectedGraph g, int s) {
// start = s;
visited = new boolean[g.V()];
pathTo = new int[g.V()];
distTo = new int[g.V()];
pathTo[s] = s;
bfs(g, s);
}
public void bfs(DirectedGraph g, int s) {
Queue queue = new LinkedList();
visited[s] = true;
distTo[s] = 0;
queue.offer(s);
while(!queue.isEmpty()) {
int v = queue.poll();
for (int w : g.adj(v)) {
if (!visited[w]){
visited[w] = true;
distTo[w] = distTo[v] + 1;
pathTo[w] = v;
queue.offer(w);
}
}
}
}
public boolean hasPathTo(int v) {
return visited[v];
}
public Iterable pathTo(int v) {
if (!hasPathTo(v)) return null;
List list = new ArrayList();
Stack stack = new Stack();
int x = v;
for (; distTo[x] != 0; x = pathTo[x]) {
stack.push(x);
}
stack.push(x);
while (!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
}