A 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).
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:
For the above-mentioned disconnected graph, the order of elements visited in the breadth-first search is:
0 1 2 3 4 5 6
You can also try this code with Online Python Compiler
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.
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.
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.
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()
You can also try this code with Online Python Compiler
#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;
}
You can also try this code with Online C++ Compiler
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.
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.
46+ registered 