Now on to the second half of the search process:

For each child of the current node
  Make a copy of the current path
  Add the child to the copy
  Append the updated path to the frontier

To ensure each child node has its own list, we need to make a copy of current_path and append the child node. Making a copy of the list is important so each child node has its own list added to the frontier. If current_path is not copied then the children will be added to the same list which will result in an incorrect path as well as only one child being searched.

Assigning a list to a new variable name does not make a copy of the original list. The new variable will still reference the same list. Python gives us multiple options to make a copy of a list each with its own reference:

original_list = ["My", "ideas", "are", "unique", "!"] copy_list1 = original_list[:] copy_list2 = original_list.copy() copy_list3 = list(original_list)

In the above example, the three copied lists can have elements added to them without affecting the original list.

In the example below we add an element to one of the copies. The output shows the copy is updated and the original list is unchanged.

copy_list1.append("See?") print(copy_list1) print(original_list) # Output # ["My", "ideas", "are", "unique", "!", "See?"] # ["My", "ideas", "are", "unique", "!"]



To create the paths for the frontier queue you now must loop through the children list in current_node and make a new path for each one.

  • Create a for loop with a loop variable called child that iterates through current_node.children.
  • Inside the loop, define the variable new_path and set it to a copy of current_path.

Add the new path with the added child to the frontier queue to keep the search going.

Inside the for loop, do the following:

  • Add child to new_path
  • Add new_path to the left side of path_queue

Test out the algorithm implementation by updating the goal value to initiate a deeper search.

  • In main.py replace the second argument in the bfs() call with the value "Fluffy.jpg".

When you run the code you should now see a longer path output, which includes the root node value, the goal node value, and all values in between.

Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?