Learn

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:

Bridge 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.

Instructions

1.

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 visited_vertices list.

2.

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.

Take this course for free

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?