Learn

The traversal search() method will be recursive, so we can backtrack and explore multiple paths within the graph. There are a few components for implementing this search:

  • The search() method should take in the vertex we are currently on as input. In its first iteration, this would be the start vertex.
  • We should first loop through the vertices list so that we can access the index for each vertex in the graph.
  • On each loop iteration, access the adj_matrix value for the current vertex and the neighbor vertex to check against.
    • If this value is 1, that means this neighbor is connected to the current vertex.
    • If visited_vertices at this index is 0, that means this neighbor has not yet been visited in the path.
    • If both of these above conditions are met, we should mark this neighbor as visited within visited_vertices by setting the value to 1. We should also add this neighbor to the path list. Next, traverse the neighbor by recursively calling search() on this neighbor vertex.

Let’s walk through one iteration of this implementation. In our bus route example, we start at “School.” As we loop through the vertices:

  • We first come across index 0 (“School”).
  • Since “School” is not connected to “School”, we continue on to index 1 (“Sajay”)
  • “School” is connected to “Sanjay” and “Sanjay” has not been visited yet, so we can set visited_vertices[1] = 1 to 1 and add “Sanjay” to the path
  • We now search what vertices are connected to “Sanjay” to find the next house along the road/route.

Instructions

1.

We check to see if the loop variable neighbor vertex is *both *connected to our current vertex and has not yet been visited. If so, we should first set the neighbor index within the visited_vertices list to visited. Modify the search() method to do this.

2.

Then, add neighbor to path since we are going to traverse it next. Implement this inside the search() method.

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?