Learn

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()
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 `.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.

### Instructions

1.

Import `deque` from the `collections` module.

2.

To implement the frontier queue, inside the `bfs()` function define a variable `path_queue` and assign it an instance of `deque()`.

3.

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 `path_queue` definition:

• Define `initial_path` and set it equal to a list with `root_node` as the only element.
• Add `initial_path` to the left side of the frontier queue.