-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBreadthFirstPaths.java
More file actions
45 lines (43 loc) · 1.08 KB
/
BreadthFirstPaths.java
File metadata and controls
45 lines (43 loc) · 1.08 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package Graph;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BreadthFirstPaths {
boolean []book;
int edgeTo[];
private int s=0;
public BreadthFirstPaths(Graph G,int s){
this.book=new boolean[G.V()];
edgeTo=new int[G.V()];
this.s=s;
bfs(G,this.s);
}
public void bfs(Graph g,int v){
Queue<Integer> que=new LinkedList<>();
que.offer(v);
book[v]=true;
while (!que.isEmpty()) {
int tmp=que.poll();
for (int i : g.adj(tmp)) {
if (!book[i]) {
edgeTo[i]=tmp;
book[i]=true;
que.add(i);
}
}
}
}
public boolean hasPathTo(int v){
return book[v];
}
public Iterable<Integer> getPath(int v){
if(hasPathTo(v)==false)
return null;
Stack<Integer> stack=new Stack<>();
for(int x=v;x!=s;x=edgeTo[x]){
stack.push(x);
}
stack.push(s);
return stack;
}
}