BFS for Disconnected Graph

Problem Statement

The problem “BFS for Disconnected Graph” states that you are given a disconnected directed graph, print the BFS traversal of the graph.

Example

The BFS traversal of the graph above gives: 0 1 2 5 3 4 6

Approach

Breadth first Search (BFS) traversal for Disconnected Directed Graph is slightly different from BFS traversal for Connected undirected graph. In a connected undirected graph, we begin traversal from any source node S and the complete graph network is visited during the traversal. However, the BFS traversal for Disconnected Directed Graph involves visiting each of the not visited nodes and perform BFS traversal starting from that node. We terminate traversal once we find that all the nodes have been visited.

Consider the connected undirected graph given below, starting BFS traversal from any node of the graph would visit all the nodes in the graph in one go.

Consider the directed connected graph below, as it is evident from the image, to visit all the nodes in the graph, it is needed to repeatedly perform BFS traversal from nodes 0, 1, 3.

Algorithm

1. Consider, there are V nodes in the given graph.
2. Iterate through each node from 0 to V and look for the 1st not visited node.
3. Begin BFS traversal starting from this node and mark all the nodes subsequently traversed as visited.
4. Terminate once all the nodes in the graph have been visited.

Code

C++ Program for BFS for Disconnected Graph

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// Add Edge from node u to v
void addEdge(vector <int> graph[], int u, int v)
{
    graph[u].push_back(v);
}

// BFS traversal function
void BFS(vector <int> graph[], int n)
{
    // vector to mark nodes as visited
    vector <bool> vis(n,false);
    
    // Process each node from 0 to n-1
    for(int i=0;i<n;i++)
    {
        // If not visited node is found
        if(vis[i] == false)
        {
            // BFS queue
            queue <int> q;
            // add not visited node to queue
            q.push(i);
            
            // BFS traversal
            while(!q.empty())
            {
                int front = q.front();
                q.pop();
                
                cout<<front<<" ";
                
                vis[front] = true;
                
                for(auto node : graph[front])
                {
                    if(vis[node] == false)
                    q.push(node);
                }
            }
        }
    }
    
    cout<<endl;
}

int main()
{
    // Construct the graph
    int n = 7;
    vector <int> graph[n];
    vector<pair<int,int>> edges = {{1,0},{1,2},{2,5},{3,4},{4,6}};
    
    for(auto e : edges)
    addEdge(graph,e.first,e.second);
    
    // Display the BFS traversal
    cout<<"BFS traversal of the given graph : ";
    BFS(graph,n);
    
    return 0;
}

BFS traversal of the given graph : 0 1 2 5 3 4 6

Java Program for BFS for Disconnected Graph

import java.util.*;
import java.io.*;

class TutorialCup
{
    // Add Edge from node u to v
    static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v)
    {
        graph.get(u).add(v);
    }
    
    // BFS traversal function
    static void BFS(ArrayList<ArrayList<Integer>> graph, int n)
    {
        // array to mark nodes as visited
        boolean [] vis = new boolean[n];
        
        // Process each node from 0 to n-1
        for(int i=0;i<n;i++)
        {
            // If not visited node is found
            if(vis[i] == false)
            {
                // BFS queue
                Queue <Integer> q = new LinkedList<>();
                // add not visited node to queue
                q.add(i);
                
                // BFS traversal
                while(!q.isEmpty())
                {
                    int front = q.poll();
                    
                    System.out.print(front+" ");
                    
                    vis[front] = true;
                    
                    Iterator itr = graph.get(front).iterator();
                    while(itr.hasNext())
                    {
                        int node = (Integer)itr.next();
                        if(vis[node] == false)
                        q.add(node);
                        
                    }
                }
            }
        }
        
        System.out.println();
    }
    
    public static void main (String[] args) 
    {
        // Construct the graph
        int n = 7;
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<n;i++)
        graph.add(new ArrayList<Integer>());
        
        int [][] edges = {{1,0},{1,2},{2,5},{3,4},{4,6}};
        for(int i=0;i<edges.length;i++)
        addEdge(graph,edges[i][0],edges[i][1]);
        
        // Display the BFS traversal
        System.out.print("BFS traversal of the given graph : ");
        BFS(graph,n);
    }
}

BFS traversal of the given graph : 0 1 2 5 3 4 6

Complexity Analysis

1. Time Complexity: T(n) = O(V+E)
2. Space Complexity: A(n) = O(V)

Because we’ve been using our space complexity becomes linear. So the algorithm becomes linear in space. And for time complexity as we have visited all the nodes in the graph. The algorithm takes linear time as well.

V = number of nodes.

E = number of edges.