Code:
import java.util.*;
public class BfsPaths {
private boolean[] marked;
private int[] edgeTo;
private int s;
public BfsPaths(Graph g, int s) {
this.marked = new boolean[g.V()];
this.edgeTo = new int[g.V()];
this.s = s;
bfs(g, s);
}
public 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]) {
edgeTo[w] = v;
marked[w] = true;
queue.add(w);
}
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
public Iterable<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;
}
public static void main(String...args) {
Graph g = new Graph(5);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(0, 3);
BfsPaths bp = new BfsPaths(g, 1);
System.out.println(bp.hasPathTo(0));
for(int i : bp.pathTo(0)) {
System.out.println(i);
}
}
}
