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<Integer> queue = new LinkedList<Integer>();

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<Integer> pathTo(int v) {

if (!hasPathTo(v)) return null;

List<Integer> list = new ArrayList<Integer>();

Stack<Integer> stack = new Stack<Integer>();

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;

}

}