This post is completed by 1 user

  • 0
 Add to List
Medium

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

  1. Use the Queue.
  2. 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.
  3. While(any unvisited vertex exist)
    1. Add the vertex to the queue. 
      1. 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. 

 

Output:

BFS:
0 2 1 3 4 6 5

Related Problems: