Problem Description
Given a directed graph. The task is to do Breadth First Traversal of this graph starting from 0.
Solution
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
46
47
48
49
50
51
52
class Solution {
// Function to return Breadth First Traversal of given graph.
public ArrayList<Integer> bfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
Queue<Integer> q = new LinkedList<>();
//initialize the queue by adding the source node, which is 0 in this case
q.add(0);
//visited array to track the nodes which have been already visited
boolean[] visited = new boolean[V];
//mark node 0 as visited
visited[0] = true;
//bfs answer list. add 0 to it
ArrayList<Integer> bfs = new ArrayList<>();
bfs.add(0);
//while queue is not empty
while(!q.isEmpty()){
//take out the node from queue
int n = q.poll();
//get the neighbours of that node
ArrayList<Integer> neighbours = adj.get(n);
//loop through all the neighbours and check if they have been visited
for(Integer x: neighbours){
//if the neighbour node has not been visited
if(visited[x] == false){
//add to answer bfs list
bfs.add(x);
//add to queue so that we can later visit its neighbours
q.add(x);
//mark it as visited so that we don't visit it again
visited[x] = true;
}
}
}
return bfs;
}
}