DEV Community

Prashant Mishra
Prashant Mishra

Posted on • Originally published at practice.geeksforgeeks.org

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.

Image description

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.
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)