Confused about recursion in python-depth first search-:

Thread Starter

terabaaphoonmein

Joined Jul 19, 2020
101
Python:
# Python dictionary to act as an adjacency list
graph = {
  '7' : ['19','21', '14'],
  '19': ['1', '12', '31'],
  '21': [],
  '14': ['23', '6'],
  '1' : [],
  '12': [],
  '31': [],
  '23': [],
  '6' : []
}

visited = [] # List of visited nodes of graph.
def dfs(visited, graph, node):
    
    if node not in visited:
        visited.append(node)


    for neighbor in graph[node]:
        dfs(visited, graph, neighbor)
    print(node)

# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '7')
print("visited=",visited)


what I don't understand is how do once this program reaches to print(1) what happens next, it doesn't make any sense to me.
idk if I am stupid or what to not realize sth very trivial or idk.

I will try to explain what is my problem, step by step.
steps-:

1) dfs(visited,graph,7)

2)
7 not in visited.
visited=7
dfs(19)

3) 19 not in visited.
visited=7,19
dfs(1)

4) 1 not in visited
visited=7,19,1
1 has no neighbours.
print(1)

imo the code should stop now. Because there is no function call no nth. But in fact the code goes to

for neighbour in graph(node):
dfs(visited,graph,neighbour)
and starts with dfs(12). I don't understand this....How does it happen?

how can it go to for loop just like that?(source-:https://cscircles.cemc.uwaterloo.ca/visualize#mode=display)

even if it doesn't go to for loop, I can't make sense where it really goes. Can you please guide me about this issue?
 

hrs

Joined Jun 13, 2014
362
You're calling a function in a function in a function. When dfs(1) is done executing, it will return to where dfs(19) left off. When dfs(19) is done executing, it will return to where dfs(7) left off. Something with a function return address and a stack. A real programmer, not me, can probably explain how this works exactly.
 

Thread Starter

terabaaphoonmein

Joined Jul 19, 2020
101
You're calling a function in a function in a function. When dfs(1) is done executing, it will return to where dfs(19) left off. When dfs(19) is done executing, it will return to where dfs(7) left off. Something with a function return address and a stack. A real programmer, not me, can probably explain how this works exactly.
https://cdn-images-1.medium.com/max/600/1*KmVggtKbQtxyWBeOr8Ks3w.png
this is helpful somewhat although it is the same thing as you said.
 

Thread Starter

terabaaphoonmein

Joined Jul 19, 2020
101
You're calling a function in a function in a function. When dfs(1) is done executing, it will return to where dfs(19) left off. When dfs(19) is done executing, it will return to where dfs(7) left off. Something with a function return address and a stack. A real programmer, not me, can probably explain how this works exactly.
1643780602481.png

in the slide instead of printing visited, we have printed node...what does that mean? shouldn't output of depth first search be how we traverse? i m not getting this last point.

slide is here(view in desktop) https://slidetodoc.com/tree-and-graph-traversal-algorithms-breadthfirst-search-bfs/
 
Top