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. 

Run This Code

Code:

Run This Code

Output:

BFS:
0 2 1 3 4 6 5

Also Read:

- Graph – Detect Cycle in an Undirected Graph using DFS Medium
- Graph Implementation – Adjacency List - Better| Set 2 Beginner
- Find the nearest building which has bike | Find nearest specific vertex from source in a graph. Hard
- Implement Graph Using Map - Java Medium
- Given Graph - Remove a vertex and all edges connect to the vertex Medium
- Dijkstra’s – Shortest Path Algorithm (SPT) – Adjacency List and Priority Queue – Java Implementation Hard
- Reverse the Directed Graph Beginner
- Find the number of distinct Islands OR connected components. Hard