Breadth-First Search in Disconnected Graph

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



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. 



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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: