Before reading further, make sure you understand what queues and graphs are.
Suppose you’re in San Francisco, and you want to go from Twin Peaks to the Golden Gate Bridge. You want to get there by bus, with the minimum number of transfers. Here are your options.
What’s your algorithm to find the path with the fewest steps?
Well, can you get there in one step? Here are all the places you can get to in one step.
The bridge isn’t highlighted; you can’t get there in one step. Can you get there in two steps?
Again, the bridge isn’t there, so you can’t get to the bridge in two steps. What about three steps?
Aha! Now the Golden Gate Bridge shows up. So it takes three steps to get from Twin Peaks to the bridge using this route.
There are other routes that will get you to the bridge too, but they’re longer (four steps). The algorithm found that the shortest route to the bridge is three steps long. This type of problem is called a shortest-path problem. You’re always trying to find the shortest something. It could be the shortest route to your friend’s house. It could be the smallest number of moves to checkmate in a game of chess. The algorithm to solve a shortest-path problem is called breadth-first search. Now, let us get into the technicalities. Breadth First Search is applied on graphs.
Breadth First Search helps us answer two kinds of questions.
Question 1: Is there a path from node A to node B?
Question 2: What is the shortest path from node A to node B?
Now, let's understand this completely with another example. Suppose your dog is looking to buy mangoes on LinkedIn.
He's connected with three people - Bob, your cat, Claire, your pig and Alice, your mouse. Let's call them 1st Degree connections.
Also, each of these people are connected to some other animals. Let's call them 2nd Degree connections of your dog.
Your dog will prefer a first-degree connection to a second-degree connection, and a second-degree connection to a third-degree connection, and so on. So he shouldn’t search any second-degree connections before he makes sure he doesn't have a first-degree connection who is a mango seller. Well, breadth-first search already does this! The way breadth-first search works, the search radiates from the starting point. So it'll check first-degree connections before second-degree connections.
We'll first explore all the nodes nearest to your dog and then explore all the nodes on the second level, the third level, and so on. (Although there are only two nodes in this example, you get the idea).
If there is an unvisited node in Breadth First Search, we can say that there is no connection between the starting point and the node.
Now, let's see how we can implement this. We use queues to implement Breadth First Search. We will refer to the graph above with the first-degree and second-degree connections. We start with an empty queue.
Now, we add the nearest connections to our starting point in our queue. From our graph, we can see that the nearest connections are Bob, Claire and Alice. So, we add all three of them in the queue (in no particular order).
Now, we will pop elements off the queue. Popping an element means that we have visited that element. After popping an element, we add neighbours of that element to our queue. So, let us visit Alice.
If Alice is a mango seller, then we have found a mango seller and we can stop our operation right here. Else if Alice is not a mango seller, we add all its neighbours to the queue.
Please note that some authors use 'enqueue' instead of 'push' and 'dequeue' instead of 'pop'. Both of them mean the same thing. We do this with all the remaining elements until we find a mango seller. Please note that if we have visited a node, we do not need to visit it again. So, for example, we have added Peggy to our queue while popping Alice. Now, when we pop Bob, we only need to add Anuj to the queue. We do not need to add Peggy again.
If we do not find a mango seller in the queue, then mango seller does not exist in the graph. This was the implementation of Breadth First Search using queues. Breadth First Search can be applied on Trees much the same way it is applied on Graphs.