Interview Kickstart has enabled over 3500 engineers to uplevel.
Learning basic graph traversal algorithms is important for any software developer to crack coding rounds of interviews at top tech companies.
Breadth-first search is one such graph algorithm, which helps solve easy as well as advanced graph problems. Knowing this algorithm can boost your chances of clearing tech interview questions on data structure and algorithms.
In this article, we cover everything you need to know about the BFS algorithm, including:
Graph traversal is the process of visiting every vertex and edge of a graph at least once. The order in which the vertices are visited is important. There may be many such orders, but the challenge is to find the traversal technique best suited to solve a particular problem.
Breadth-first search (BFS) is a graph search and traverse algorithm used to solve many programming and real-life problems. It follows a simple, level-based approach. We can easily solve many problems in computer science by modeling them in terms of graphs. For example: analyzing networks, mapping routes, scheduling, and more.
The BFS algorithm traverses the graph across its breadth. It's a layerwise traversal algorithm. BFS starts traversing the graph from a chosen “root” node, say Source, and explores all of its neighbor nodes at its next depth before moving on to the other nodes.
Let’s look at the algorithm to understand this better.
Let’s take an example. We’ll use an undirected graph with six vertices.
We first choose a node to start BFS and put it in the queue after marking it “visited.” In this case, we have chosen 0.
We will repeatedly pop the front element of the queue, traverse its neighboring nodes, and add it to “BFS Order.” Currently, we have 0 at the front of the queue, and none of its neighbors are visited. So, we’ll mark them as visited and add all of them to the queue.
Now, we have node 1 at the front of the queue. It has only two neighbors, 0 and 3, which have been marked visited in a previous step. So, we'll move on to the next step.
Here, we have 3 at the front of the queue. It has only one unvisited neighbor, 4. So, we will mark it visited and add it to the queue.
For node 2, we add its unvisited neighbor 5 to the queue.
For node 4, all its neighbors are already visited — we move on to the next step.
After extracting 5 from the queue, all the graph elements have been visited, and there are no elements left in the queue. BFS on this graph is complete.
If you look closely, you will notice that we have visited the nodes layerwise, that is, in the order of their level. Let’s understand what that means.
A level structure of an undirected graph is a partition of the vertices into subsets that are at the same distance from a given root vertex. Here:
Now, if you observe the obtained BFS Order, we have visited the nodes in the order of their levels.
Getting the hang of it? Here’s the pseudocode for BFS. Go ahead and implement it in a programming language of your choice.
We’ve chosen C++ to demonstrate how the code works. You can implement the same in C, Java, Python, or any other programming language.
The BFS Traversal is:
0 1 3 2 4 5
In this algorithm, we traverse each edge and each node at least once. Therefore, the time complexity can be expressed as O(V + E) — here, V is the number of nodes and E is the number of edges.
It is important to note that the number of edges in a graph can vary from 0 to n * (n -1) / 2 in an undirected graph. And so:
Another implementation of BFS uses an adjacency matrix instead of an adjacency list (which we have used here) for storing the graph. In that case, the time complexity will always be O(V2).
If the graph is a tree, then the complexity becomes O(V), as the number of edges in a tree equals one less than the number of vertices.
The space complexity of the algorithm is O(V). In both implementations of BFS (using adjacency list and adjacency matrix), the extra space required is in the order of V (for the queue and the boolean vector visited).
The space required for the graph representation is O(V + E) for an adjacency list and O(V2) for an adjacency matrix representation.
In the above implementation, we assumed that the graph is connected — all the nodes are reachable from any node. But, we may have to work on disconnected graphs too in some scenarios.
With a little modification to the above implementation, we can apply BFS on disconnected graphs too.
Following is an example of a disconnected graph (with 8 nodes) and the program to traverse the graph using BFS.
The BFS Traversal is:
0 1 3 2 4
5 6 7
To learn more, check out our article on depth-first search.
Question 1: How can BFS be used to detect a cycle in an undirected graph?
Answer: We can detect if an undirected graph has a cycle by performing a BFS traversal of the given graph. For every visited vertex “v,” if there is an adjacent “u” such that u is already visited and u is not a parent of v, then there is a cycle in the graph.
If we don’t find such an adjacent node for any vertex, we can conclude that there is no cycle in the graph. Note that we have assumed that there are no parallel edges between any two vertices in the graph; otherwise, we can say that the graph contains a cycle without even applying BFS.
Question 2: Why does BFS use the “queue” data structure over other data structures like “stack”?
Answer: The First In First Out (FIFO) concept of a queue ensures that things that are discovered first are explored first, before exploring those that are discovered subsequently — this is the key for this algorithm. Therefore, a queue is the most optimum data structure for implementing BFS.
Stacks are exactly the opposite of queues. Stacks apply the Last In First Out (LIFO) concept, which is optimum for the depth-first search algorithm.
Question 3: Can we find the shortest path between two nodes using BFS?
Answer: We can find the shortest paths between nodes using BFS but only for an unweighted graph. For a given node “u” of a connected graph “G,” we can find the shortest path between u and all other nodes of the graph G by applying BFS on the graph with the root node as u.
We can do this by storing the immediate parent of each node in an array while visiting the vertices in the BFS function and then creating the path for each node using the parent array. The parent of a node is its neighbor that was visited the earliest.
Let’s suppose we have the parent array “p” of size “V,” for a graph G with V vertices, and node 0 is the root. Suppose we want to find the path between the root node and all the other nodes of the graph:
For all i, where 0 < i < V holds, Let pi be the parent of node i. p can be set as -1.
The following pseudocode will do the job:
Note that the above pseudocode will print the path in reversed order.
Question 4: Is BFS a complete and optimal algorithm?
Answer: If an algorithm is complete, it means that if at least one solution exists, then the algorithm is guaranteed to find a solution in a finite amount of time.
If a search algorithm is optimal, it means when it finds a solution, it finds the best solution.
BFS is both complete and optimal.
Basic graph traversal algorithms can help you solve many questions during your tech interview as a software developer. If you’re looking for guidance and support to nail these questions and more, sign up for our free webinar.
As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
Article contributed by Shivam Gupta