Hoping you’ll support the YouTube channel just like you have greatly supported the website! 🙂
Hello people…! In this post I will explain one of the most widely used Graph Search Algorithms, the Breadth First Search (BFS) Algorithm. Once you have learned this, you would have gained a new weapon in your arsenal, and you can start solving good number of Graph Theory related competitive programming questions.
What we do in a BFS is a simple step-by-step process, which is –
- Start from a vertex S. Let this vertex be at, what is called…. “Level 0”.
- Find all the other vertices that are immediately accessible from this starting vertex S, i.e., they are only a single edge away (the adjacent vertices).
- Mark these adjacent vertices to be at “Level 1”.
- There will be a challenge that you might be coming back to the same vertex due to a loop or a ring in the graph. If this happens your BFS will take ∞ time. So, you will go only to those vertices who do not have their “Level” set to some value.
- Mark which is the parent vertex of the current vertex you’re at, i.e., the vertex from which you accessed the current vertex. Do this for all the vertices at Level 1.
- Now, find all those vertices that are a single edge away from all the vertices which are at “Level 1”. These new set of vertices will be at “Level 2”.
- Repeat this process until you run out of graph.
This might sound heavy… Well atleast it would sound heavy to me if I heard it for the first time…! Many questions may pop-up in your mind, like, “How are we gonna do all that…?!”. Well, for now, focus on the concept, we will talk about the code later. And remember, we are talking about an Undirected Graph here. We will talk about Directed Graphs later. To understand the above stated steps, examine the picture below –
The sketch clearly shows you how we explore the vertices adjacent to a vertex and mark their levels. If you have noticed, whenever there were two ways of accessing the same vertex from multiple vertices of the same Level, i.e., in the diagram, Vertex 3 was accessible from Vertex 2 and Vertex 8, we preferred its parent to be Vertex 8, the larger number. Why is that so…? We will learn that in a short moment.
The concepts that I wish to emphasize from the above picture are, how BFS can tell you the shortest path from a given vertex (the start vertex) to all the other vertices and the number of edges or, the “length of the path”, would be the Level of that Vertex itself. This is a very important feature of the BFS, you will understand this more clearly when I explain it with the help of an example in a different post.
Now, having got some knowledge about the BFS, it is a good thing to do an exercise on this topic to really get the flow going. Try applying BFS on the Graph given. All you have to do is to implement the step-by-step process and get that final figure which I got above. And make sure you label the Levels and Parents for each vertex in the end.
Now, we come to the code part of the Breadth First Search, in C. We use the same Adjacency List that we used in our discussion of Graph Theory Basics. Coming back to our BFS discussion, the level of each vertex is stored in a separate array and so is the case for parent of each vertex. The three arrays are initialized to appropriate values. Now recall our step-by-step process that was stated earlier. Try to put that in terms of pseudocode and then proper code. Take a while to think how you would do that. If you could code it, you are marvelous…! 😀 … If not, don’t fret, I put my code below…!
Try using the above example given as practice as the sample input to your code, so that you can easily compare the results. Now, the important point here is when we insert a vertex into the Adjacency List, we follow Head Insertion to get O(1) Insertion. What happens due to this is that, the Linked List will have numbers in the descending order.
So, when we are applying BFS for adjacent vertices of a given node, the Vertex with the higher number is met first. And then we explore starting by that higher numbered Vertex. This is why whenever we had a choice in approaching a vertex, we preferred approaching from the vertex which had the bigger number, why…? Due to Head Insertion…! If you had used Tail Insertion, this would be reversed.
This is the overview of Breadth First Search Algorithm. It has a computational complexity of O(|V| + |E|), which is pretty fast. But why O(|V| + |E|)…? If you think about the algorithm a little bit, we cover all the |V| vertices level-by-level, checking all the |E| edges twice (for an Undirected Graph). Once the level is set for a subset of vertices we don’t visit them again. Put an itty-bitty thought into it and I’m sure you’ll get the idea…! 😉 … But, the code above runs slower than O(|V| + |E|)… To achieve the proper complexity we must use a Queue.
We can use BFS in the following scenarios –
- Shortest Path or Quickest Path (if all edges have equal weight).
- Finding the Length of Shortest Path between two Vertices.
With the knowledge of BFS you can start solving Graph Theory related problems. It really depends on your logic how you will apply the BFS to the given problem. And there is only one way to develop it… Practice…! So, keep practicing… Feel free to comment your doubts..! Happy Coding…! 🙂
25 thoughts on “Breadth First Search Algorithm”
correct me if i m wrong!!
in the bfs function (just implementing the bfs by using c) ,suppose for a particular vertex we get two levels ,what should be the level of that vertex??wont we be comparing it with the prevous value??(if i m finding the distance between two vertices,that should be its level,then that had to be the minimum value??)
The level of a vertex would be whatever it is set to when you visit it for the first time. When you encounter a vertex with its level already set, then you should simply ignore that vertex because it is already traversed.
So in your terms, if a vertex gets 2 levels, ignore the second as the 1st will always be lesser.
Thank you!
Thank you. It really helped me understand.
Glad to help! 🙂
Great tutorial
Thank you! 🙂
Great article!
Software development and programming algorithms are not easy to explain and understand but you did a great job 🙂 Its really easy to understand and drawings help a lot!
Thank you! 🙂
🙂
A great article! I believe there is an error in the version using the queue…
while (itr != adjacencyList[newVertex].end()) {
if (level[*itr] == -1) { // This is an unvisited vertex
level[*itr] = lev + 1; // Set level
parent[*itr] = newVertex; // Set parent
VertexQueue.push_back(*itr); // Add it to the queue
}
++itr;
}
The “lev” gets incremented on each “pop”. I believe that instead the level should be that of the parent plus one. e.g.
level[*itr] = level[newVertex] + 1; // level is one more than the parent
That’s actually a huge bug!… The code looks different from my archived codes… Don’t know where that crept from… Thanks a lot for pointing it out! 🙂
Hello…Here you have implemented BFS for weighted tree/graph but i think it might give wrong answer for some cases like-(undirected graph)
A is conn to B,C with distance 4,1.
C is conn to B with 2.
B,C is conn to D with dist 5,3.
Here algo might give (A)——4—–(B)——5—–(D) as shortest path between A to C (dist=9) but actual one is (A)——1—–(C)——3—–(D) (dist=4)
I’m sorry, I didn’t get you… I have implemented BFS for an unweighted graph.
you have written :
adjacencyList[v1].push_back(v2);
why is not this written?
adjacencyList[v2].push_back(v1);
it is a undirected graph . it should be both ways.
Yeah, it is undirected, corrected the code 🙂
Hi excellent variant of the BFS. However, when should i use a pure BFS with O(|V|+|E|) and when this variant. if i only need traversal right? Is there any benefit i should use this BFS implementation with 3 loops? What is the time complexity of this algorithm. More specifically how many iterations the while(flag) loop takes in the worst case. My guess is O((|V|^2).|E|).
Yes, you are right… To understand the worst case complexity of this algorithm, take the innermost while loop. What are we doing there? We are checking out all the neighbours of a vertex. Now theoretically, in BFS we know that for each vertex we check out its neighbours once… So, the worst case complexity becomes O(|V|2), which happens in a fully connected graph where there’s an edge between each pair of vertices. So, for a fully connected graph you are checking out the neighbours at each vertex which costs O(|V|) time and you do this for each vertex, so totally it is O(|V|2). The while(flag) loop runs as many as the (maximum level + 1) times, where maximum level is the last level formed in the given graph… For example, for the fully connected graph, the maximum level is 1… So your while(flag) loop runs twice… If you have a linearly connected graph, the iterations become O(|V|) as you will have |V| – 1 levels… I hope you get it 😛 … Do comment if you have any more questions 🙂
Why you have used the list in vector?
I just wanted it to visually resemble the C implementation as much as possible… In C we use a an array where each element is a pointer to linked list… Here too, I am using a vector (which resembles the array), where each element is a list (which resembles the linked list)… Hope that made sense 😛
this program use stack in bfs which is not true in case of bfs
I’m not sure I get you properly… This program doesn’t use a stack…. Its a simple iterative procedure… If you here looking for the BFS implemented using a Queue, here’s the link … 🙂
I have a doubt in line “The Linked List will have numbers in the descending order”
How linked list have number in descending order?
Can you explain this by taking example ?
Sorry for the late reply… It just occurs here because our input has the vertices ordered in an increasing fashion and we follow head insertion. Let’s say we insert 1, 2, 3 into the linked list. Firstly the list will have 1 inserted which is fine. Then, 2 is inserted at the head, so the linked list is now 2 -> 1 -> NULL. Now we insert 3 in the head, so our linked list looks like, 3 -> 2 -> 1 -> NULL. This is why I said it is in a descending order. This doesn’t necessarily happen always. 🙂