Once we have completed and recursively traversed a neighbor vertex, we should backtrack from that vertex to explore other paths and cycles that may exist in the graph.
Backtracking allows us to find additional solutions to our problem by removing (backtracking from) failed candidates and trying a different path that may lead to a solution that meets all constraints.
For example, consider a graph that leads to a dead-end vertex where there is no edge to connect us to the remainder of vertices in the graph. Once we reach this dead-end vertex, we will want to backtrack so that we can potentially find another path that will allow us to visit all vertices. Consider this graph:
If we first searched the path A > C > D > E, we would see that not all nodes have been visited and will need to backtrack to find another path that meets the criteria for a Hamiltonian path.
To implement this backtracking:
- After calling the recursive
search()on the neighbor node, set the neighbor index back to unvisited in the visited_vertices list. This is done by setting the value back to 0.
- Pop the neighbor node from the path list.
Imagine to the left of our “School” vertex is a connected 6th vertex “Ben” that isn’t connected to anything else.
- If we started at “School” and visited “Ben”, we would reach a dead-end and have several unvisited nodes left.
- This path would not be an eligible bus route, so we would need to backtrack back to “School” and visit “Sanjay” instead.
Let’s modify our
search() method to include this backtracking.
Imagine the scenario where we get to the hypothetical vertex “Ben” and realize that there is no eligible Hamiltonian path. We need backtrack back to the “School” vertex and we need to “unvisit” the “Ben” node so that we can try a new path and ensure it will only visited once.
Implement the logic to set the neighbor node that we just visited back to 0 within the
Since the hypothetical “Ben” path is ineligible to be a Hamiltonian path, we will want to pop the “Ben” vertex from the
path list as we backtrack out to find an eligible path.
Implement the logic to pop the neighbor node from the path.