Breadth-First Search in Disconnected Graph

Objective: Given a disconnected graph, Write a program to do the BFS, Breadth-First Search or traversal.

Example:

Approach:

Earlier we had seen the BFS for a connected graph. In this article, we will extend the solution for the disconnected graph.

  • Use the Queue.
  • Create a boolean array, mark the vertex true in the array once visited. This array will help in avoiding going in loops and to make sure all the vertices are visited.
  • While(any unvisited vertex exist)
    • Add the vertex to the queue. 
      • While the queue is not empty.
        1. Remove a vertex v from the queue.
        2. Print the vertex v.
        3. Mark the vertex v true in the boolean array.
        4. Add all the unvisited adjacent vertices of v to the queue. 

Code:

Output:

BFS:
0 2 1 3 4 6 5

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: