Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 📃
2.
Problem Statement 💬
2.1.
Example 💢
2.1.1.
Explanation 😎
3.
Solution Approach ✅
3.1.
Python Implementation 📌
3.2.
C++ Implementation 📌
4.
Complexities 📋
4.1.
Time Complexity ⏳
4.2.
Auxiliary Space Complexity 💾
5.
Frequently Asked Questions ❔
5.1.
Does BFS also work with disconnected graphs?
5.2.
What is the time complexity of the BFS algorithm?
5.3.
What is the auxiliary space complexity of the BFS algorithm? and why?
5.4.
How many times is a vertex visited in BFS?
5.5.
What is a disconnected graph?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

BFS in Disconnected Graph

Author Teesha Goyal
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction 📃

Graph is a non-linear data structure that stores elements(as vertices) and connections between them(as edged). In a disconnected graph, all the vertices are not connected with all the other vertices(directly or indirectly). 

Introduction to graphs

This article discusses the concept of performing Breadth-First-Search(BFS) in a disconnected graph.

Problem Statement 💬

You are given a disconnected graph, and you need to perform a breadth-first search and print the elements of the graph. An adjacency list gives the connections(or edges). You have to ensure that all the vertices are printed in the result. 

Example 💢

The given disconnected graph is as shown below:

Example

For the above-mentioned disconnected graph, the order of elements visited in the breadth-first search is: 

0 1 2 3 4 5 6

Explanation 😎

When we start with vertex 0, vertices 1 and 2 are added to the queue, and via vertex 1, vertex 3 is added. Since the graph is disconnected, vertex 4, 5, and 6 can not be visited by any visited vertex. So we have to start the BFS again with vertex 4; now, vertices 5 and 6 are visited. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution Approach ✅

Solution approach

Traversing a disconnected graph in BFS differs from traversing a connected graph. The main difference is that not all the vertices of a disconnected graph can be visited using all other vertices. So after implementing BFS, you have to check whether or not all the vertices are visited. If some vertices remain, you must implement BFS again with that vertex. 

To learn more about BFS in Connected graph, visit Breadth-First Search - Coding Ninjas Coding Ninjas Studio
 

The approach/algorithm of BFS in the disconnected graph is as follows:

  • Use a boolean array Visited to keep track of the visited vertices. 
  • Intialize a queue to keep track vertices. 
  • For each vertex i, check whether vertex i is visited or not. If the vertex is not visited, implement simple BFS:
    • Add the vertex i to the queue
    • While the queue is not empty 
      • Remove the front element t from the queue and print it
      • Mark True for vertex t in the Visited array.
      • Add all the unvisited adjacent vertices of t to the queue using the adjacency list.

Solution approach 1

Solution approach 2

Python Implementation 📌

import queue
 
'''Function to add an edge'''
def Edge(adj, v1, v2):
    '''For undirected graph adding forward and backward edge'''
    adj[v1].append(v2)
    adj[v2].append(v1)
 
'''Simple BFS function'''
def BFS(v1, adj, Visited):
 
    '''Initialize Queue'''
    queue_of_vertices = queue.Queue()
     
    '''Add the starting vertex to queue'''
    queue_of_vertices.put(v1)
    Visited[v1] = True
   
    '''While queue is not empty, keep visiting the front vertex'''
    while(not queue_of_vertices.empty()):
         
        '''Remove the front vertex'''
        v1 = queue_of_vertices.queue[0]
        queue_of_vertices.get()
       
        '''Print current vertex'''
        print(v1, end = " ")
       
        '''Add the unvisited adjacent vertices of v1 to the queue'''
        i = 0
        while i != len(adj[v1]):
            if (Visited[adj[v1][i]] is not True):
                    Visited[adj[v1][i]] = True
                    queue_of_vertices.put(adj[v1][i])
            i += 1
   
'''Driver Function'''
def main():
   
    '''Creating the adjacency list for the graph '''
    number_of_vertices = 7
    adj = [[] for i in range(number_of_vertices)]
 
    '''Adding edges'''
    Edge(adj, 0, 1)
    Edge(adj, 0, 2)
    Edge(adj, 1, 2)
    Edge(adj, 1, 3)
    Edge(adj, 2, 3)
    Edge(adj, 4, 5)
    Edge(adj, 4, 6)
   
    '''Implementing BFS for disconnected graph '''
    Visited = [False for i in range(number_of_vertices)]
    for vertex in range(number_of_vertices):
        if(not Visited[vertex]):
            BFS(vertex, adj, Visited)
   
'''Executing Main'''
main()

 

C++ Implementation 📌

#include<bits/stdc++.h>
using namespace std;
 
/* Function to add an Edge */
void Edge(vector<int> adj[], int v1, int v2)
{
    /* considering undirected graph, hence adding both forward and backward edge */
    adj[v1].push_back(v2);
    adj[v2].push_back(v1);
}
 
/* Simple BFS Function */
void BFS(int v1, vector<int> adj[], vector<bool> &Visited)
{
    /* Initialize a queue for keeping track of upcoming vertices */
    list<int> queue_of_vertices;
 
    /* Mark the current vertex visited and pushed to the queue*/
    Visited[v1] = true;
    queue_of_vertices.push_back(v1);
 
    /* while the queue is not empty, keep on traversing */
    while(!queue_of_vertices.empty())
    {
        /* remove the front vertex and print it*/
        v1 = queue_of_vertices.front();
        cout << v1 << " ";
        queue_of_vertices.pop_front();
 
        /* Add all the unvisited adjacent vertices of v1 to the queue */
        for (int iter = 0; iter != adj[v1].size(); iter++)
        {
            if (!Visited[adj[v1][iter]])
            {
                Visited[adj[v1][iter]] = true;
                queue_of_vertices.push_back(adj[v1][iter]);
            }
        }
    }
}
 
/* Driver Function */
int main()
{
    int number_of_vertices = 7;
    vector<int> adj[number_of_vertices];
 
    /* Adding edges */
    Edge(adj, 0, 1);
    Edge(adj, 0, 2);
    Edge(adj, 1, 2);
    Edge(adj, 1, 3);
    Edge(adj, 2, 3);
    Edge(adj, 4, 5);
    Edge(adj, 4, 6);
   
    vector<bool> Visited(number_of_vertices, false);
    for (int u=0; u<number_of_vertices; u++)
        if (Visited[u] == false)
            BFS(u, adj, Visited);
           
    return 0;
}

Complexities 📋

Time Complexity ⏳

O(V + E), where V and E represent the number of vertices and the number of edges, respectively. 

Reason: Even though we are running an extra loop in this algorithm, the time complexity is still the same as the time complexity of running BFS in a connected graph because the idea of visiting a vertex only once remains the same. 

Auxiliary Space Complexity 💾

O(V), where V is total number of vertices.

Reason: The Visited array requires a space equal to the number of vertices (V) to keep track of the visited vertices. Also, the same amount of memory is required to store vertices in the queue.

Also check out: Application of graph data structure

Frequently Asked Questions ❔

Does BFS also work with disconnected graphs?

The conventional/straightforward BFS approach does not work with the disconnected graphs as not all the vertices are connected with all the other vertices. But, with a modification in the simple approach, you can make BFS work for disconnected graphs too. 

What is the time complexity of the BFS algorithm?

The time complexity of the BFS algorithm is the same for both connected and disconnected graphs and is equal to O(number_of_vertices + number_of_edges).

What is the auxiliary space complexity of the BFS algorithm? and why?

The auxiliary space complexity of the BFS algorithm is O(V), where V is the number of vertices. The additional space is required to store the vertices in the visited array and the queue. 

How many times is a vertex visited in BFS?

In the BFS algorithm, each vertex is visited mandatorily and only once. No vertex is visited twice or more. A Boolean Visited array is used to keep track and make sure you visit each vertex only once.

What is a disconnected graph?

In a disconnected graph, all the vertices are not connected with all the other vertices(directly or indirectly). It is created by two or more connected graphs being unconnected but part of a single disconnected graph. 

Conclusion

This article discussed the concept of performing Breadth-First-Search(BFS) in a disconnected graph.

To learn more about BFS in Connected graph, visit Breadth-First Search - Coding Ninjas Coding Ninjas Studio

I hope you would have gained a better understanding of these topics now!
Check out this problem - No of Spanning Trees in a Graph

Are you planning to ace the interviews with reputed product-based companies like AmazonGoogleMicrosoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!

Previous article
Best First Search or Informed Search
Next article
BFS Using Vectors & Queue as per the Algorithm of CLRS
Live masterclass