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
pathlist. This means that a Hamiltonian path has been found. Append it to thehpathslist 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
startvertex and the number of vertices we have visited in ourpathlist 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 thecycleslist.- 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.