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:
search()method should take in the vertex we are currently on as input. In its first iteration, this would be the
- We should first loop through the
verticeslist so that we can access the index for each vertex in the graph.
- On each loop iteration, access the
adj_matrixvalue 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.
visited_verticesat 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_verticesby setting the value to 1. We should also add this neighbor to the
pathlist. 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 = 1to 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.
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.
path since we are going to traverse it next. Implement this inside the