DFS with recursion and without stack

Question

this is my code to implement DFS with recursion but no stack. I ran few test cases which turned out to be positive but wanted to check the efficiency of the code.

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'E']),
         'D': set(['B', 'F']),
         'E': set(['C', 'B', 'F']),
         'F': set(['D', 'E'])}
visited_nodes = set()
is_visited = {}
#seen_nodes = set()
seen_nodes = []



def unseen_neighbors(start_node):
    unseen = []
    for i in graph[start_node]:
        if is_visited.get(i, 'NA') == 'NA':
            unseen.append(i)
    print ('start node and unseen ', start_node, unseen)
    return unseen



def DFS(graph, start_node):
    is_visited[start_node] = True
    #seen_nodes.append(start_node)
    #print ('seen ', seen_nodes)
    #add_neighbors(start_node)
    unseen = unseen_neighbors(start_node)
    if len(unseen) == 0:
        return
    for i in unseen:
        if is_visited.get(i, 'NA') == 'NA':
            seen_nodes.append(i)
            DFS(graph, i)

if __name__ == "__main__":
    seen_nodes.append('A')
    DFS(graph, 'A')
    print ("DFS Traversal ", seen_nodes, set(seen_nodes))

Answer 1

Well, your code is indeed doing DFS and it is doing tail recursion. I don't see any improvement from an algorithm perspective. One low-hanging fruit is to get rid of seen_nodes as it seems to exist only for debugging purposes.