PROBLEM DESCRIPTION
Given a directed graph. The task is to do Breadth First Traversal of this graph starting from 0.
SOLUTION
We use a queue to explore nodes level by level, marking each node as visited once it’s processed. For each node, we visit its unvisited neighbors, mark them as visited, and add them to the queue.
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
class Solution {
public ArrayList<Integer> bfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
ArrayList<Integer> list = new ArrayList<>();
Queue<Integer> q = new LinkedList<>();
q.add(0);
boolean[] visited = new boolean[V];
visited[0] = true;
while(!q.isEmpty()){
int current = q.poll();
list.add(current);
ArrayList<Integer> neighbors = adj.get(current);
for(Integer neighbor: neighbors){
if(!visited[neighbor]){
visited[neighbor] = true;
q.add(neighbor);
}
}
}
return list;
}
}