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 thehpaths
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 ourpath
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 thecycles
list.- This means we have started at “School”, picked up every student, and are back at the “School” vertex.
Instructions
Review the stop condition implementation within script.py
to understand the conditional checks that will determine if a Hamiltonian path and/or cycle exist.
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.