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

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.