Learn

Since the search() method is recursive, we need to provide an exit condition, otherwise we could end up in an infinite loop searching the graph. We should add this exit condition to the beginning of our search() method.

The exit condition should be checked first in the search() method. Before exiting the recursion, we should check if:

  • All vertices have been visited, and there are no duplicate vertices in the path list. This means that a Hamiltonian path has been found. Append it to the hpaths list if so.
    • In our bus route scenario, this means that we have started at “School” and every student has been picked up and that we may or may not be back at the “School” vertex by the end of the path.
  • The current vertex equals the start vertex and the number of vertices we have visited in our path list equals the number of vertices in our vertices list, plus 1. We must add 1 here since the starting vertex will show in this list twice. If we meet this condition, we should add the path to the cycles list.
    • This means we have started at “School”, picked up every student, and are back at the “School” vertex.

Instructions

1.

Review the stop condition implementation within script.py to understand the conditional checks that will determine if a Hamiltonian path and/or cycle exist.

2.

Execute the full code on the school bus route graph/adjacency matrix. You should get the following Hamiltonian paths and cycles found:

Hamiltonian paths:[0, 1, 2, 3, 4], [0, 4, 3, 2, 1]

Hamiltonian cycles:[0, 1, 2, 3, 4, 0], [0, 4, 3, 2, 1, 0]

If you do not get the above results, recheck your search() method logic.

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?