Breadth First Search Algorithm in Python
Problem Introduction
Have you ever thought about the fact that all programming tasks can be expressed through connected graphs and that most of the cases the solution is to traverse the graph according to a specific order?
Just think about the case where a player in a video game needs to be able to find the fastest way to escape a maze.
At the moment I don’t want to bore you with graph theory and how you can implement graphs in Python. For this reason I attach you one of my old articles where everything is well explained.
One of the best ways to solve the maze problem is using the breadth first search algorithm.
Suppose you start from the first cell and you need to reach the exit as soon as possible. We can represent the use case in the figure above:
To reach the exit port we can do the steps “1–5-exit” or “4–8-exit”.
How I said before this problem could be solved with the help of the graph search, actually we will specifically deal with the case in which starting from a root node the exit is reached by crossing all the nodes at each level of the tree.
For the sake of semplicity we can let the agent move only right and down starting from the first position. In this way we get a binary tree describing each movement done.
In this figure, each node indicate the cell and each branch represent the step or better the movement from a cell to another. The BFS (breadth first search algorithm) iterations follow the red numbers order.
At the beginning the algorithm searches for the new cells to the right and at the bottom of the current position, subsequently for each of the generated cells (if the end is not reached) it generates other cells at each level of the tree. Then, for each level, all the children of each node are explored.
Code
But so what is the pseudocode of the BFS? The pseudo-code seems very easy and it can be summarized in these few lines
BFS (G, s) //Where G is the graph and s is the source node
let Q be queue.
Q.enqueue( s ) //Inserting s in queue until all its neighbour vertices are marked.
mark s as visited.
while ( Q is not empty)
//Removing that vertex from queue,whose neighbour will be visited now
v = Q.dequeue( )
//processing all the neighbours of v
for all neighbours w of v in Graph G
if w is not visited
Q.enqueue( w ) //Stores w in Q to further visit its neighbour
mark w as visited.Source: https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/
Now we are going to transform this code in Python, applying it to the problem described above.
At first we create the matrix that represent our Maze.
So it has an output like this:
[‘start’, 1, 2, 3]
[4, 5, 6, 7]
[8, ‘EXIT’, 9, 10]
[‘EXIT’, 11, 12, 13]
Next step is to create an object that represent the node of the tree. Since Python is an OOP language, we can do this through a Node class:
As we can see it is a simple class that build a node with its own value, its own coordinates and moreover it knows its father node.
Before to get inside the algorithm cycle, it is good to set the margins where the agent cannot exceed (the height and width of the room). Then, a root node is instantiated and inserted as the first element of a list which will be the fringe of the tree at each iteration.
The main part of the whole code is this while loop:
This code takes a node from the fringe list (the first node is the root) and then it checks if it is the end of the journey, if it’ s not so new children nodes are generated (corrisponding to the turn right or turn down).
Note that if it finds the end of the path, it creates a list that contains all the nodes that are crossed, simply by recursively identifying all the parent nodes starting from the last node corresponding to the exit.
If we merge all the parts presented we get this code:
Output of the code:
[‘start’, 1, 2, 3]
[4, 5, 6, 7]
[8, ‘EXIT’, 9, 10]
[‘EXIT’, 11, 12, 13]
Shortest path: [‘start’, 1, 5, ‘EXIT’]
Conclusion
What we described is only one of the ways to cross the tree built basing on movements made by an agent.
In the next article we will see how to use another tree traversal algorithm that explores the entire hierarchy of a node starting from the root, rather than exploring the nodes level by level, it s called Depth First Search Algorithm.