Breadth First Search Traversal of Graph GeeksForGeeks

For traversing only the connected components:
Problem:
Given a directed graph. The task is to do Breadth First Traversal of this graph starting from 0.
Note: One can move from node u to node v only if there's an edge from u to v and find the BFS traversal of the graph starting from the 0th vertex, from left to right according to the graph. Also, you should only take nodes directly or indirectly connected from Node 0 in consideration.



Input: 
Output: 0 1 2 3 4
Explanation: 
0 is connected to 1 , 2 , 3.
2 is connected to 4.
so starting from 0, it will go to 1 then 2
then 3.After this 2 to 4, thus bfs will be
0 1 2 3 4.

Solution: TC O(n) as we will be visiting atmost n Nodes, and space complexity: O(n)



//in bfs, we tarverse a node and adjacent nodes of the traversed node.
/*          0
      /     |     \
   1         2        3
             |
            4
*/
//bfs : 0-> 1->2->3->4
class Solution {
    // Function to return Breadth First Traversal of given graph.
    public ArrayList<Integer> bfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
        ArrayList<Integer> bfs = new ArrayList<>();
        boolean visited[] = new boolean[V];
        // this is for traversing connected graph only 
            if(!visited[0]){
                Queue<Integer> queue = new LinkedList<>();
                visited[0] = true;
                queue.add(0);

                while(!queue.isEmpty()){
                    Integer node = queue.remove();
                    bfs.add(node);

                    for(Integer adjNode : adj.get(node)){
                        if(!visited[adjNode]){
                            visited[adjNode] = true;
                            queue.add(adjNode);
                        }
                    }  
                }
            }
        return bfs;
    }
}

For traversing entire graph including the not connected graph components



class Solution {
    // Function to return Breadth First Traversal of given graph.
    public ArrayList<Integer> bfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
        ArrayList<Integer> bfs = new ArrayList<>();

        boolean visited[] = new boolean[V];
        // for traversing the entire graph
        for(int i =0;i<V;i++){
            if(!visited[i]){
                Queue<Integer> queue = new LinkedList<>();
                visited[i] = true;
                queue.add(i);

                while(!queue.isEmpty()){
                    Integer node = queue.remove();
                    bfs.add(node);

                    for(Integer adjNode : adj.get(node)){
                        if(!visited[adjNode]){
                            visited[adjNode] = true;
                            queue.add(adjNode);
                        }
                    }
                }
            }
        }
        return bfs;
    }
}

Blog

Breadth First Search Traversal of Graph GeeksForGeeks

Prashant Mishra

Join Our Newsletter. No Spam, Only the good stuff.

Related