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 .pop() method.

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([1])
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([3])
q.pop() // #q = deque([])
while q:
  print("In the loop") # No Output

In this example:

• The first element added to the queue using .appendleft() is 1.
• The first element removed from the queue using .pop() is 1.
• We used len() on a deque() object to get the number of elements in q.
• A deque() object as a while condition loops when there are elements in the queue and exits the loop when the queue is empty.