A Quick Guide to Breadth-First Search
In this article, we will discuss the breadth-first search or bfs algorithm. The breadth-first search algorithm for graphs is similar to the breadth-first search algorithm for trees. The only difference is, since a graph may contain a cycle so we may encounter the same node again and again. To avoid dealing with the same node again, we can divide the set of vertices into two categories:
2. Not visited
For this purpose, a boolean array is maintained to mark the nodes that we have encountered yet. In breadth first search algorithm, the queue is used for the traversal.
Implementation of Breadth first search algorithm
1. The very first step is to declare a queue and push the starting vertex or root.
2. Then, we need to initialize a visited array and mark it as visited.
3. We need to keep doing the following processes until our queue gets empty:
- Get the vertex stored at the front of the queue and mark it as visited.
- Remove this vertex from the queue.
- Explore all the direct neighbours of this vertex and insert them in the queue.
The following is the implementation code of breadth first search algorithm:
Time complexity: O(V + E) where V signifies the number of vertices and E signifies the number of edges
Space complexity: O(V) where V signifies the number of vertices
Breadth-first search for disconnected graph
A graph unlike a tree may be disconnected. In that case, we need to tweak our code a little bit. Consider the following program in which we loop over all vertices so that we don’t miss out any component:
As you can see, all the nodes have been traversed.
In this article, we discussed the breadth first search algorithm in graph. We also learned about how we can traverse a disconnected graph. We believe that you must have learned something new through this article.