# BFS for Disconnected Graph

Difficulty Level Easy
Frequently asked in Amazon Hulu Karat Microsoft Salesforce
Breadth First Search Graph Graph Traversal

## 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.
Postfix to Infix Conversion

## 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)

// 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)
{
}

// 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

// 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)

}
}
}
}

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++)

int [][] edges = {{1,0},{1,2},{2,5},{3,4},{4,6}};
for(int i=0;i<edges.length;i++)

// 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)