Feb 25
Breadth First Search(BFS) Algorithm In Python Part 1
Before we dive into this algorithm, let’s first consider its purpose and the reasons behind its development.
Breadth First Search (BFS) is a graph traversal algorithm that was first described by Konrad Zuse in 1945 as a part of his work on the first high-level programming language, Plankalkül. However, the algorithm gained more widespread recognition when it was independently rediscovered by E.F. Moore in 1959 and then by C. Y. Lee in 1961
It was developed to solve the problem of finding the shortest path in a graph, which is useful in many real-life scenarios, such as network routing, social network analysis, and web crawling. The algorithm starts at a root node and explores all the nodes at the current depth level before moving on to the next level. By visiting all the nodes in a breadth-first manner, the algorithm can find the shortest path between the root node and any other node in the graph. The BFS algorithm has since been widely used in various fields, including computer science, operations research, and social sciences.
The technical aspects:
The Queue:
The queue follows the first-in, first-out (FIFO) principle, which means that the first element added to the queue is the first one to be removed.
In BFS, when a node is added to the queue, it is added along with its depth level, and nodes are visited in the order they are dequeued from the queue, this guarantees that nodes will be visited level by level, from the shallowest depth level to the deepest level.
For example, let’s consider the following graph:
When we start at node A, we add it to the queue and mark it as visited. The queue initially contains one node with depth level 0, which is the starting node A. After visiting A, we add its neighbors to the queue and mark them as visited, and they will have a depth level of 1. The queue now contains three nodes B, C, and D, with a depth level of 1.
When we dequeue the first node from the queue, it will be B, then we visit its neighbors and mark them as visited, they will have a depth level of 2, and add them to the queue. The queue now contains two nodes E and F, with a depth level of 2.
By following this process, we are guaranteed that we will visit all the nodes at the current depth level before moving on to the next depth level. This guarantees that we will find the shortest path in an unweighted graph because we are guaranteed to find the shortest path to a node before finding any longer paths to the same node.
Meaning of visiting a node.
Visiting a node in the context of BFS and DFS means performing a specific action on the node, this action can vary depending on the application or the problem that the algorithm is trying to solve.
For example, in a graph traversal problem, visiting a node may mean printing or marking the node as visited.
In the shortest path problem, visiting a node may mean updating the distance from the source node to the current node. In a search problem, visiting a node may mean checking if the current node is the goal node.
Meaning of exploring a node.
Exploring a node in the context of BFS and DFS means visiting a node, and adding its unvisited neighbors to the queue or stack for future visits. It is an essential step in both BFS and DFS, allowing the algorithm to traverse the graph and visit new nodes.
For example, refer to the graph/tree above:
If we start at node A, and we want to use BFS to traverse this graph:
- We start at node A, we add it to the queue and mark it as visited.
- We dequeue the first node from the queue, which is A, and we explore it by visiting its unvisited neighbors B, C, and D, and adding them to the queue.
- We dequeue the next node from the queue, which is B, and we explore it by visiting its unvisited neighbors E and F and adding them to the queue.
- We dequeue the next node from the queue, which is C, and we explore it by visiting its unvisited neighbor G, and adding it to the queue.
- We dequeue the next node from the queue, which is D, there are no unvisited neighbors, so we do not add any new nodes to the queue.
- We dequeue the next node from the queue, which is E, there are no unvisited neighbors, so we do not add any new nodes to the queue.
- We dequeue the next node from the queue, which is F, there are no unvisited neighbors, so we do not add any new nodes to the queue.
- We dequeue the last node from the queue, which is G, there are no unvisited neighbors, so we do not add any new nodes to the queue.
At this point, the queue is empty, and we have visited all the nodes in the graph.
Example Implementation of Breadth First Search (BFS) to find the shortest path in an X-Y cartesian coordinate system:
The Graph class has three methods: add_node, add_wall, and breadth_first_search.
The add_node method adds a new node to the graph at the specified coordinates. The add_wall method adds a new wall node to the graph at the specified coordinates. The breadth_first_search method takes two nodes as input, start_node, and end_node, and performs a breadth-first search to find the shortest path between them. The method returns a list of coordinates representing the shortest path.
The algorithm starts by adding the start_node to a queue and marking it as visited. It then enters a loop that continues until the queue is empty. In each iteration of the loop, it removes the first node from the queue and checks if it is the end_node. If it is, it returns the shortest path by tracing back through the parent pointers from the end_node to the start_node. Otherwise, it adds all the unvisited neighboring nodes of the current node that are not walls to the queue and marks them as visited, setting their parent pointer to the current node.
The get_neighbours method returns a list of neighboring nodes of a given node, and the get_path method traces back through the parent pointers from the end_node to the start_node to return the shortest path.
The code also includes an example usage of the Graph class, where a new graph is created with dimensions 5x5, walls are added at specific nodes, and the BFS algorithm is used to find the shortest path between two nodes.
To add support for diagonal paths in the given BFS code, we need to modify the get_neighbours function of the Graph class. Currently, this function only returns the four adjacent nodes of the current node. We need to modify it to include the four diagonal nodes as well.
Here’s the modified code for get_neighbours the function:
In the modified code, we use two loops to generate all eight neighbors of the current node (including the diagonal neighbors). We skip the node itself by checking that both the x and y offsets are zero. We then calculate the x and y coordinates of the neighbor using the offsets and add them to the neighbours list only if the neighbor is within the bounds of the graph.
With this modification, the breadth_first_search the function will now consider diagonal paths as well while searching for the shortest path between the start node and the end node.
In addition, we can consider adding some optimizations such as checking if the start_node and end_node are the same or if they are walls before running the algorithm to avoid unnecessary computation. We can also use a deque instead of a list to implement the queue for better performance. Additionally, we can consider using a set or a boolean array to keep track of visited nodes instead of using the visited attribute of each node. Finally, we can implement the A* algorithm instead of BFS to find a more optimized path.
In the upcoming article, we will explore how to visually trace the shortest path using a breadth-first search algorithm with the Tkinter Python library. This will give us a better understanding of how the algorithm works in real-world applications and demonstrate how this setup can be useful in developing a maze solver that can be incorporated into game development.
Here is the code for part 1: https://gist.github.com/Sebuliba-Adrian/92f9690eb624f3bff2efd750f259d0fe
