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
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 the
hpathslist 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 our
pathlist 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
- This means we have started at “School”, picked up every student, and are back at the “School” vertex.
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.