Welcome back, dear reader. So, how is it going for you till here? We hope that you are learning a lot. So, in this article, we will be learning something called the BREADTH FIRST TRAVERSAL of a graph. We recommend you watch the Breadth First Traversal Video before moving on with this article as it will be easier for you to understand it from the video first than directly coming to the article. Let us now not waste any time and dive straight away to learn the Breadth First traversal.
Breadth First Traversal
It's hard to find an error in your code if you are looking for it. It's harder to find it if you believe your code is error-free.
Let us say we have a graph as shown in the figure:
In this graph, we are given the source vertex as vertex 2. We have to print the breadth first traversal of the graph given vertex 2 as the source vertex. We will learn the exact meaning and definition of the breadth first traversal along the way, implementing the procedure.
For now, let us just give you one hint. The breadth-first traversal of a graph is similar to the level-order traversal of a tree. We will look at this too when we move forward with the procedure.
We request you to just follow the procedure we tell you side-by-side yourself and you will be able to understand the breadth first traversal of a graph completely.
As we mentioned above, the breadth first traversal of a graph is similar to the level order traversal of a tree. So, do you remember the level order of a tree? Which data structure we used to print the level-order of a generic tree and a binary tree? Yes, we used the queue data structure and we implemented the algorithm "remove-print-add". If you do not remember the level order traversal of a binary tree, refer to the LEVEL ORDER OF GENERIC TREE and the LEVEL ORDER OF BINARY TREE questions and try to solve these problems first. Refer to the solution videos of LEVEL ORDER OF A GENERIC TREE and LEVEL ORDER OF A BINARY TREE to understand the use of queue data-structure and the "remove-print-add" algorithm.
Here we will perform the following steps: r m* w a*
r --> remove w --> work
m --> mark a --> add
What is this procedure? It does sound similar to the remove print and add but what is the "mark" and "work" here? What do these star symbols mean? Let's discuss all of this now:
Let us start our procedure. We will insert the source vertex and the path till the source vertex into the empty queue first.
The 2-2 inserted in the queue represents the source vertex 2 and the path till 2 is only 2. Now, the first step from r m* w a* i.e. remove will be carried out. So, we will remove the element from the queue and we mark the vertex 2 with a star depicting that we have visited it.
The next step is w i.e. work. What is the work that we have to do here? We have to print. So, that is what we will do. Now, the last step is to add. We have to add the neighbors of this vertex i.e. vertex 2 to the queue and we have to add only those vertices which are not marked. The above procedure is shown in the diagram below (fig-3)
So, we removed 2-2 from the queue and marked a star on it depicting that it has been visited. Then, we did the work of printing and 2@2 got printed i.e. path till 2 is 2. Then, we added the neighbors of vertex 2 into the queue and we added them in such a way that the vertex name was the name of the vertex and the path was modified by writing the vertex after the previous path. For instance, we added 1 into the queue and the path which came from the previous vertex i.e. 2 was appended with this vertex. So, this means we added 1-21 meaning that the path till vertex 1 (1-) is 21 (1-21) i.e. from source vertex 2 visit to vertex 1.
We strongly recommend you watch the solution video to understand the process till here completely and to develop a better understanding of this process.
Here we would like to draw your attention to a very interesting point. We have added the neighbors of vertex 2 into the queue and we added vertex 1 first and then we added vertex 3. If you think carefully, both are just the vertices (neighboring vertices) which are to an equal distance from the vertex 2. So, it doesn't really matter which vertex we insert first. If we would have inserted the vertices in the reverse order i.e. we would have inserted 3 first and then the vertex 2, the answer for the Breadth first traversal would have differed definitely but, conceptually, it is not wrong to insert any vertex before or after.
The thing which we want to convey is that if we do not take care of the order in which we are inserting the vertices into the queue, we will still get Breadth First Traversal of the tree, but it would be different.
From this, we have got an idea that the breadth first search is not about the order of the elements in which they appear in a graph, it is something else. What exactly is it? Let's perform our r m* w a* algorithm once more and then we will find out the exact meaning of breadth first traversal.
Til now, the condition of our queue and graph is as follows (this is fig-4 only)
Now, let us apply our procedure once more. We will remove the element at the front of the queue, then, we will mark it with a star, print it and insert its neighbors (only the unmarked ones) into the queue. The diagram below shows the queue after the process is completed:
Now, we will do the procedure again. We will remove 3-23, mark the vertex, print it and add its unmarked neighbors to the queue.
Now you might be wondering a few things. Firstly, we still don't know the exact meaning of Breadth first traversal and also that we have added 0 twice in the queue. Once when we added the neighbors of 1 and also when we added the neighbors of 3. Is that wrong or correct?
If you have a look at the tree representation currently, you will see that at each level, the vertices that are present are at an equal distance from the source vertex 2. For instance, 2 itself is at 0 distance from 2 and there is no other vertex at that level. Also, in the next level, we have vertices 1 and 3, both at a distance of 1 edge from the source vertex 2. At the next level, we have 0 and 4, both at a distance of 2 edges from the source vertex.
So, breadth first traversal of a graph from a source vertex v is the traversal which gives us the vertices whose distance radially increases from the source vertex v.
That is why we discussed earlier that you can keep the neighboring vertices in the queue in any order you want as their sequence does not matter. The only thing which matters is their distance from the source vertex.
So, yes, there are more than one Breadth First Traversals for a graph (by changing the order of the neighboring queues).
Now, the second question. Why did 0 get inserted twice? This is because 0 is at a distance of 2 units from 2 paths via 2-1-0 and 2-3-0. So, inserting 0 twice is correct.
So, we hope that you have now understood the meaning of Breadth First Traversal and why there can be more than one breadth first traversal for a given graph. Now, we recommend that you follow the same algorithm and do this hard work of visualizing the queue, tree and graph and trace the entire breadth first traversal yourself. We recommend you watch the solution video to understand the complete tracing of the tree and meaning of breadth first traversal in a deep way. Now that we have understood the complete method, let's write the code for it.
You may refer to the solution video to understand the above code completely and resolve your doubts if any. Now, we will discuss the time and space complexity for Breadth first Traversal.
The adding and removing of elements from the queue takes O(1) time. Since we are traversing every vertex of the graph to print its breadth first traversal, the time taken will be O(n).
Since we have used a queue data structure, the space complexity of the above method is O(n)
So, we hope that you have understood the time and space complexity of the procedure also. With this we have completed this problem. You may refer to the complete solution video once to make your concepts strong and clear all your doubts.
Here are some suggestions from our side that you do not want to miss:
- We suggest that you should watch the complete solution video twice as it will clear most of your doubts and will make your concept really strong.
- We also suggest that you should dry run the code with the procedure that we have studied above to get the complete insight. See, breadth first traversal of a graph is a really important topic and you can see numerous problems on this topic on any coding platform and in any coding test/interview. So, it is our suggestion that you spend time on this problem so that it becomes your strength rather than your weakness for solving further problems. Till then, Happy Coding!!!