Breadth First Search(BFS) Algorithm In Python Part 1
Before we proceed with the mechanics of this algorithm, we must first establish the motivations behind its inception and its objectives. The Breadth First Search (BFS) algorithm is a graph traversal technique. It was introduced by Konrad Zuse in 1945 during his efforts towards creating Plankalkül, which is recognized as one of the earliest high-level programming languages. However, it wasn’t until E.F Moore rediscovered it independently in 1959, followed by C.Y Lee’s recognition two years later, that BFS received wider attention.
The motivation for developing BFS was the need to locate the shortest path within a graph, a crucial aspect with numerous practical applications. These applications span various domains such as network routing, web crawling, and even social network analysis, which are extensively used today. The BFS approach commences from a root node and explores each node at that specific depth before proceeding to the next layer. This breadth-first traversal allows it to determine the most direct route between any graph node and its root.
The BFS algorithm has gained significant popularity over the years and is extensively utilized across various fields including computer science, operations research, and social sciences. In the context of Breadth-First Search (BFS), the Queue holds significant importance from a technical standpoint. It operates on the FIFO principle — elements present at an earlier position in the queue get removed before anything else. In BFS specifically, when a node is added to this Queue, its depth level is stored along with it.
The dequeue operation follows this order: nodes get dequeued in their original enqueued sequence. This ensures that BFS visits nodes according to their levels of depth only, starting with shallower ones and reaching deeper levels eventually.
To aid in better comprehension, let’s consider an example graph.
Beginning at node A, we queue it up and mark it as visited. The starting node A is the only node in the queue that has depth level 0. We add A’s neighbors to the queue after visiting A, label them as visited, and give them a depth level of 1. Three nodes, B, C, and D, with a depth level of 1, are now present in the queue.
B will be the first node to be removed from the queue after which its neighbors, who have a depth level of 2, are visited, marked as visited, and then added to the queue. Two nodes, E and F, with a depth level of 2, are present in the queue right now.
By using this procedure, we ensure that we visit all of the nodes at the current depth level before going on to the next depth level. This ensures that we will discover the shortest path in an unweighted network since we will find the shortest path to a node before any longer pathways to the same node.
Meaning of visiting a node.
In the context of BFS and DFS, visiting a node refers to carrying out a specific action on the node; the action might change based on the application or the issue that the algorithm is attempting to address.
For instance, in a graph traversal issue, publishing or marking a node as visited may be considered visiting that node.
The distance from the source node to the current node may need to be updated when a node is visited in the shortest route issue. Visit a node in a search issue may involve determining whether the present node is the goal node.
Meaning of exploring a node.
In the parlance of Breadth-First Search (BFS) and Depth-First Search (DFS), exploring a node is defined as visiting the said node and subsequently adding its unvisited neighbors to the queue or stack for impending visits. This process is integral to the functioning of both BFS and DFS, given that it enables the algorithm to traverse the entirety of the network and visit nodes that have not yet been visited.
Consider the illustrative example of the graph or tree as depicted above. If the starting point is node A, and BFS is utilized to traverse this graph, the following steps would be carried out:
1. Begin at node A, add it to the queue, and mark it as visited.
2. Dequeue the first node from the queue, which in this case is A. Proceed to explore A by visiting its unvisited neighbors B, C, and D, and adding them to the queue.
3. Dequeue the subsequent node from the queue, which is node B. Explore B by visiting its unvisited neighbors E and F, and adding them to the queue.
4. Dequeue the next node, C, from the queue. Explore C by visiting its unvisited neighbor G, and adding it to the queue.
5. Dequeue the next node, D, from the queue. As there are no unvisited neighbors of D, no new nodes are added to the queue.
6. Dequeue the next node, E, from the queue. Similarly, E does not have any unvisited neighbors, thus no new nodes are added to the queue.
7. Dequeue the next node, F, from the queue. As F also has no unvisited neighbors, no new nodes are added to the queue.
8. Dequeue the final node from the queue, which is node G. Since G does not have any unvisited neighbors, no new nodes are added to the queue.
Upon reaching this stage, the queue is now empty, and all the nodes in the graph have been visited.
The subsequent section will present an example implementation of the Breadth-First Search (BFS) to ascertain the shortest path in an X-Y cartesian coordinate system:
The Graph class encapsulates three methods: `add_node`, `add_wall`, and `breadth_first_search`. The `add_node` method integrates a new node into the graph at the specified coordinates, while the `add_wall` method introduces a new wall node at defined coordinates. The `breadth_first_search` method accepts two nodes as input — `start_node` and `end_node` — and executes a breadth-first search to discover the shortest path between the two nodes. This method returns a list of coordinates delineating the shortest path.
The algorithm initiates the process by introducing the `start_node` into a queue and subsequently marking it as visited. Following this, the algorithm enters a loop that persists until the queue is devoid of nodes. During each iteration of the loop, the first node is removed from the queue and verified to ascertain if it is the `end_node`. Should it be the `end_node`, the algorithm returns the shortest path by retracing the parent pointers from the `end_node` back to the `start_node`. Alternatively, if the node is not the end_node, all unvisited neighboring nodes of the current node that do not constitute walls are added to the queue, marked as visited, and their parent pointer is set to the current node.
The `get_neighbours` method yields a list of neighboring nodes of a given node, while the `get_path` method retraces the parent pointers from the end_node back to the `start_node`, returning the shortest path.
Furthermore, the code includes an example of the usage of the Graph class, wherein a new graph of dimensions 5x5 is constructed, walls are established at specific nodes, and the BFS algorithm is employed to discover the shortest path between two nodes.
To incorporate support for diagonal paths in the provided BFS code, the `get_neighbours` function within the Graph class must be adjusted. Currently, this function yields only the four directly adjacent nodes of the current node. Modifications are required to include the four diagonally adjacent nodes as well.
The revised code for the `get_neighbours` function is as follows:
In the amended code, two loops are employed to generate all eight neighbors of the current node, inclusive of the diagonal neighbors. The node itself is excluded by verifying that both the x and y offsets are zero. Subsequently, the x and y coordinates of the neighbor are calculated using the offsets and are appended to the neighbors list, provided that the neighbor is within the boundaries of the graph.
As a result of this modification, the `breadth_first_search` function will now take into account diagonal paths while seeking the shortest path between the start and end nodes.
Further optimizations may also be implemented, such as verifying if the `start_node` and `end_node` are identical or if they constitute walls prior to executing the algorithm, thus mitigating unnecessary computations. Moreover, a deque could be employed as an alternative to a list for the implementation of the queue, resulting in enhanced performance. In addition, either a set or a boolean array could be utilized to track visited nodes, as opposed to using the visited attribute of each node. Lastly, the A* algorithm could be employed in lieu of BFS to determine a more optimized path.
In a forthcoming article, the visual tracing of the shortest path using a breadth-first search algorithm with the Tkinter Python library will be explored. This demonstration will offer a superior understanding of the practical applications of the algorithm and will showcase how such a setup can be instrumental in the development of a maze solver for game development.
Here is the code for part 1: https://gist.github.com/Sebuliba-Adrian/92f9690eb624f3bff2efd750f259d0fe