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 thestart
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 thepath
list. Next, traverse the neighbor by recursively callingsearch()
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.