With the function created, we will now start the algorithm by initializing the frontier queue. In this implementation, the frontier queue is called
path_queue and will hold a list for each node that needs to be searched. These nodes are known as frontier nodes. Each list in the queue acts as a path such that the first element of each list will be
root_node followed by child nodes ending with the frontier node.
We will use the
deque() python class as the frontier queue. To use
deque as a queue, we will add elements with the
.appendleft() method and remove elements with the
The following is an example of
deque() used as a classic first-in-first-out (FIFO) queue:
from collections import deque q = deque() q.appendleft(1) #q = deque() q.appendleft(2) #q = deque([2, 1]) q.appendleft(3) #q = deque([3, 2, 1]) print(len(q)) # outputs 3 q.pop() // #q = deque([3, 2]) q.pop() // #q = deque() q.pop() // #q = deque() while q: print("In the loop") # No Output
In this example:
- The first element added to the queue using
- The first element removed from the queue using
- We used
deque()object to get the number of elements in
deque()object as a
whilecondition loops when there are elements in the queue and exits the loop when the queue is empty.
deque from the
To implement the frontier queue, inside the
bfs() function define a variable
path_queue and assign it an instance of
With the frontier queue initialized, you now need a path list to add to it. Since each path begins with
root_node and the only frontier node is
root_node, the path list will have
root_node as the only element.
Do the following in the
bfs() function under the
initial_pathand set it equal to a list with
root_nodeas the only element.
initial_pathto the left side of the frontier queue.