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()
is1
. - The first element removed from the queue using
.pop()
is1
. - We used
len()
on adeque()
object to get the number of elements inq
. - A
deque()
object as awhile
condition loops when there are elements in the queue and exits the loop when the queue is empty.
Instructions
Import deque
from the collections
module.
To implement the frontier queue, inside the bfs()
function define a variable path_queue
and assign it an instance of deque()
.
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 withroot_node
as the only element. - Add
initial_path
to the left side of the frontier queue.