package Graph;
import java.util.*;
public class BreadthFirstSearch {
private boolean[] visited;
private int[] edgeTo;
private int start;
public BreadthFirstSearch(Graph g, int start) {
this.start = start;
visited = new boolean[g.V()];
edgeTo = new int[g.V()];
bfs(g, start);
}
public void bfs(Graph g, int start) {
Queue queue = new LinkedList();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int front = queue.poll();
for (int neighbor : g.adj(front)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
edgeTo[neighbor] = front;
queue.offer(neighbor);
}
}
}
}
public boolean hasPathTo(int v) {return visited[v];}
public Iterable pathTo(int v) {
List path = new ArrayList();
Stack stack = new Stack();
for (int x = v; x != start; x = edgeTo[x]) {
stack.push(x);
}
stack.push(start);
while(!stack.isEmpty()) {
path.add(stack.pop());
}
return path;
}
}