# Bidirectional Search

Hello people! In this post we will talk about Bidirectional Search, a powerful search strategy which can be used if you have a goal directed agent in a (possibly infinite) search space. The idea behind Bidirectional search is to run two simultaneous searches, one forward from the source state and the other backward from the goal, hoping that the two searches meet somewhere in the middle.

In this post we will talk about Bidirectional Breadth First Search, where we apply BFS from the source and goal simultaneously until search routes intersect. Visually, the way regular BFS would progress would be something like this –

But if we applied BFS simultaneously from source (S) and goal (G), visually it would look something like this –

We can already start to seem some improvement as the number of vertices visited would be lesser.

In terms of complexity, if branching factor is b, and distance from source to goal is d, then, BFS would take O(bd), but Bidirectional search would take O(bd/2 + bd/2) ⇒ O(bd/2), which is quite better than O(bd). So in many cases a bidirectional search is faster as the amount of exploration done is lesser.

## Properties of Bidirectional search

• Our goal in Bidirectional search is to find a path from source to goal.
• We can use any search algorithm on both sides, Bidirectional search is more of a strategy than a fixed algorithm. Using BFS on both sides is the most popular option as it guarantees an optimal path.
• Bidirectional search must be used only when your goal is well defined. Eg. for a Rubik’s cube, your goal is to fill each side with one color, which is your goal and your current configuration of cube is your source state. We could use Bidirectional search in this scenario. But in chess, your goal is to checkmate the other player, but a checkmate can happen in thousands of ways. Bidirectional search isn’t feasible in chess.
• Bidirectional search using BFS needs the edge weights to be same or non-existent. So usually Bidirectional BFS is used in undirected unweighted graphs.

## Code

Writing the code for Bidirectional BFS is easier if you have already written the code for Breadth First Search using queue. Basically, all the variables we used in BFS get doubled here. That is, for Bidirectional BFS, we will use 2 queues and 2 parent arrays. One set will be used for applying BFS from source and other set will be used for applying BFS from goal. So we can call them –

• sourceParent – the parent array to construct paths for BFS from source vertex.
• sourceQueue – the queue for BFS from source vertex.
• goalParent – the parent array to construct paths for BFS from goal vertex.
• goalQueue – the queue for BFS from goal vertex.

Although we are using a separate set of variables for BFS from source and goal, the way in which they operate will be the same, i.e., the steps like picking first element in queue, enqueuing its adjacent vertices, etc. We can put that logic in a separate method called BFSExplore().

So how will we know if the BFS from source and goal have an intersecting node? After expanding a layer on either side, we will check if a vertex has been marked as visited in both of the BFS. If yes, then that is our intersection node. Recall, that we can check if a vertex has been visited if its parent value has been set.

Now the only thing left is to return the final path. There’s no genius logic for this, just do it in a brute force way 😛 . Add all vertices from source → intersecting_vertex using sourceParent into a collection. Then add all the vertices from intersecting_vertex → goal using goalParent into the same collection. Be careful, don’t add the intersecting_vertex twice in the path 😉

I have given you all the theory you need to write the code for Bidirectional BFS. It may take some time, but do try your best to write the code yourself. You can refer to my code below if you get stuck –

I hope this has given you a good understanding of Bidirectional search. Keep practicing! Happy coding! 😀

# Snakes and Ladders Game Code

Note – Theory of Programming is shifting to YouTube! This post has a video. Watch it at – https://youtu.be/a3_QGPthIDU
Hoping you’ll support the YouTube channel just like you have greatly supported the website! 🙂

Hello people…! In this post, we will discuss about the Snakes and Ladders Game Code, where we find the shortest path to win the Snakes and Ladders game by using the Breadth First Search (BFS) Algorithm. If you don’t know the algorithm, I suggest you read my post on Breadth First Search Algorithm.

Now, Graph Theory has many applications and I love working with things that have real-world applications, well, off course the other data structures too have their uses, but the speciality of Graph Theory is its applications have the closest association with our day-to-day activities. And to show you this and to set an example on how the BFS is actually put into action, I am taking up the example of the very popular game, Snakes and Ladders.

This game needs no introduction. We all must have played it in our childhood. I will explain you, how by using Graphs and BFS we can find the Shortest Path to win the game, and, we will state that path and the number of moves of dice it takes too. Have a good look at the Snakes and Ladder board below, we will be using it as an example throughout this post.

You can see we can reach the finish block by an number of ways, but how do you find out the best…? More importantly, how do you put it as code…? That’s what we are going to do. Now, think of how you can represent the game board in terms of a Graph, by Graph I mean in terms of Vertices and Edges.

Don’t be too hard on yourself… Just take the first 7 blocks and try working out on paper what would be the Edge and what would be the Vertices. If you ponder upon this, it is very easy to tell that the numbered blocks on the game board will be our Vertices, then, what will be the Edges…? This depends on how you can go from one block to another on rolling the dice. For now, forget about the ladders and the snakes, just draw the graph for a small portion of the board. It should look somewhat similar to what is in the picture below –

Dice Roll from Block 1

As you see we would have six ways to leave block 1, depending on the dice roll. Same would be the case for block 2, or, block 3, and so on. Now, there is a very important point to be noted here… Remember, this is Directed Graph…! Because, once you roll 5 and go to block 6, there’s no way to come back. So, the directions are important. Now, let us push up the complexity a bit by adding a ladder to our above sketch in block 6, think what would happen to the edges…?

Dice Roll for Block 1 – 5

If you roll 5 from block 1 you will jump directly to block 27. So is for block 2 when you roll out 4, or, block 3 when you roll out 3 and so on. Now, “logically” speaking, the block 6 does not exists in our graph…! Think about the statement for a while. Whenever you reach block, you are directly jumping to block 27, you don’t stay there. Now, if you were constructing an Adjacency List for this graph…. In the list of adjacent vertices for Vertex 1, would you have Vertex 6 in the list, or Vertex 27…? Vertex 27 of course…! Being at Vertex 6 means being at Vertex 27…!

That is why, our edge arrow did not end at Vertex 6… See it…? One more thing, in your Adjacency List, in the list of adjacent vertices for Vertex 6, what would you have…? Nothing…! Because you cannot come to a situation where you would have to stay on Vertex 6 and roll the dice. So the adjacent nodes list corresponding to Vertex 6 should be empty. These two things are very important, when you implement the Adjacency List for the Snake and Ladder board.

Same would be the case, if a snake was there at a block. Logically that block will not exist as a vertex in our adjacency list, and the corresponding edges must be removed. The only difference being that, the edge created due to a snake can lead you to a block of lower value.

Dice Roll for Block 25

Just to get a better idea of the scenario of a ladder and snake, I have depicted what the Adjacency List would look like for the above two examples shown in the pictures.

That pic should really clarify all the confusion about the graph. If you still don’t get it, feel free to comment your query…! Now, what do we do once we have the Adjacency List ready…? We just call the Breadth First Search method on that list…! Wait… Really…?! That’s it…? Yes…!

You see the hardest part here in solving the Snakes and Ladder by graphs is correctly determining what your Vertices and Edges are. Once you get that, all you have to do is the Breadth First Search in the resultant graph. Then you can get the shortest path from Vertex 1 to Vertex 100. Now, try getting the Adjacency Lit correct and simply call the BFS method. I’m sure you will succeed if you put in a little dedication. But for those who tried and failed. I have put my code below. Before you look at my code, there are a few logics I have used –

• In the beginning of the program, I added all the edges as though the Game Board had no snakes or ladders at all (these number of edges is what I printed), then, I removed the respective edges concerning the snakes and ladders one-by-one.
• When a Vertex ‘n’ has a ladder or a snake, we are supposed to replace the corresponding edges as I depicted in the pictures above, for that, I replaced the Vertex n‘s edge with the new value, in Vertices (n – 1), (n – 2), (n – 3), (n – 4), (n – 5), (n – 6). Because it is only in these vertices that you can find an edge of vertex n.
• I put all this replacing stuff in a function replace() which takes the Linked List and searches for a value ‘oldVertex’ and replaces it with the value ‘newVertex’ when it finds it.
• I used an extra element in my array to make them 1 – index based.
• The number of moves to complete the shortest path would be the level of the last vertex, Vertex 100. Why…?! Think about it for a minute and you’ll get it…!
• I have added a recursive function, printShortestPath() which recursively looks at the parent of each vertex until the start vertex is reached. It keeps printing vertices as the recursion stack keeps popping out, thus we get the path in a reverse order. Think about this for a while… Trust me… It is easy…! 😉
```
```

If you can solve this problem, then you can solve Snakes and Ladders: The Quickest Way Up problem of HackerRank. You can think of extending this to a 20 ✗ 20 Snakes and Ladder board or an nn board. You just have to add n2 edges to the graph. Solving puzzles by Graph Theory is real fun. I hope this post helped you. If you have any doubts, feel free to comment them. Keep practicing… and… Happy Coding…! 🙂

# Breadth First Search Algorithm

Note – Theory of Programming is shifting to YouTube! This post has a video. Watch it at – https://youtu.be/5mG-qBRhvKQ
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 –

1. Start from a vertex S. Let this vertex be at, what is called…. “Level 0”.
2. 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).
3. Mark these adjacent vertices to be at “Level 1”.
4. 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.
5. 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.
6. 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”.
7. 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 –

Breadth First Search Algorithm – Step-by-Step

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.

Breadth First Search Practise Question

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…!

CC++ STLC++ STL (using a Queue)Java
```
```
[/code]
```
```
```
```
```
```

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.

### Other Implementations of BFS

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…! 🙂