Confused about recursion in python-depth first search-:

[shivajikobardan]

# 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)

[/CODE]

 

 

 

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?

 

[Ghideon]

The format of the post is tricky to follow but there is a loop for each neighbour, hence each neighbour node will be visited.

1 hour ago, shivajikobardan said:

for neighbor in graph[node]:

        dfs(visited, graph, neighbor)

 

Note the recursive call to dfs(), are you familiar with the recursive construct and how execution continues?

 

1 hour ago, shivajikobardan said:

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)

 

You need to take into account the recursive call stack; what happens after print(1)? Isn't next loop lap a call to dfs? 

dfs(visited,graph,12)

 

[Sensei]

General tip:

Search net for "python online debugger". It will give you for example:

https://www.onlinegdb.com/online_python_debugger

Copy'n'paste code, and debug it, step-in, step-out, step-over etc. Observe what Python interpreter is doing. Observe how variables change every line.