Question

Python3 question.

Suppose I have a undirect and unweighted graph with vertex list type, here is the code of the graph.

graph = { "a" : ["c"],
          "b" : ["c", "e"],
          "c" : ["a", "b", "d", "e"],
          "d" : ["c"],
          "e" : ["c", "b"],
          "f" : []
        }

I want to use this to create a DFS method. How can I use recursion only to finish the work?

Answer 1

Pseudo Algorithm for Depth First Traversal:

DFS(v,G):
   visited[v] = True

   repeat{
           for all vertices w adj. to v do{
               if(visited[w]==False)
                   DFS(w,G)
           }
   }

Python Code for solving the problem:

# global variable for storing the order in which the nodes were visited
node_visiting_order_list = []

# helper function for recursively performing depth first traversal
def DFS_actual(node,graph,visited):
   visited[node] = True
   node_visiting_order_list.append(node)

   for vertex in graph[node]:
       if not visited[vertex]:
           DFS_actual(vertex,graph,visited)
   return

# function for depth first traversal of the tree
def DFS(node,graph):
   visited = {}
   for vertex in graph:
       visited[vertex] = False

   node_visiting_order_list = []
   DFS_actual(node,graph,visited)

# main function
def main():
   global node_visiting_order_list
  
   # defining the graph(as dictionary)
   graph = { "a" : ["c"],
       "b" : ["c", "e"],
           "c" : ["a", "b", "d", "e"],
           "d" : ["c"],
           "e" : ["c", "b"],
           "f" : []
   }

   # list of all the nodes in the graph
   nodes = []
   for vertex in graph:
       nodes.append(vertex)

   # iterating over all the vertices in the graph  
   for node in nodes:
       DFS(node,graph)
       print("Following is Depth First Traversal (starting from vertex "+node+" ):")
       print(node_visiting_order_list)  
       node_visiting_order_list = [] # re-initializing the list

if __name__ == '__main__':
main()   

Snapshot of the console output: