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([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.

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.

Sign up to start coding

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?