-
Notifications
You must be signed in to change notification settings - Fork 0
/
BFS.java
38 lines (35 loc) · 1.2 KB
/
BFS.java
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
import java.util.*;
public class Solution {
public static ArrayList<Integer> BFS(int vertex, int edges[][]){
ArrayList<TreeSet<Integer>> adjList = new ArrayList<>();
for(int i=0;i<vertex;i++){
adjList.add(new TreeSet<Integer>());
}
for(int j=0;j<edges[0].length;j++){
adjList.get(edges[0][j]).add(edges[1][j]);
}
for(int j=0;j<edges[1].length;j++){
adjList.get(edges[1][j]).add(edges[0][j]);
}
ArrayList<Integer> bfs = new ArrayList<>();
Queue<Integer> q = new LinkedList<>();
boolean[] vis = new boolean[vertex];
for(int i=0;i<vertex;i++){
if(!vis[i]){
q.add(i);
vis[i] = true;
while (!q.isEmpty()) {
Integer node = q.poll();
bfs.add(node);
for (Integer cur: adjList.get(node)) {
if (!vis[cur]) {
vis[cur] = true;
q.add(cur);
}
}
}
}
}
return bfs;
}
}