Problem 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
- Consider, there are V nodes in the given graph.
- Iterate through each node from 0 to V and look for the 1st not visited node.
- Begin BFS traversal starting from this node and mark all the nodes subsequently traversed as visited.
- 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
- Time Complexity: T(n) = O(V+E)
- 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.