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.