# Confused about recursion in python-depth first search-:

shivajikobardan
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?

Gold Member
MHB
Check your indentation of the for loop. It is currently in line with the if block but you want to run it only if that condition is false right? Also it shouldn't stop at 1 completely but it will partially stop at 1.

I think it should go visited = [7,19,1,12,31...]

shivajikobardan
Check your indentation of the for loop. It is currently in line with the if block but you want to run it only if that condition is false right? Also it shouldn't stop at 1 completely but it will partially stop at 1.

I think it should go visited = [7,19,1,12,31...]
yes you are right about visited. but I don't understand how once print(1) happens, how it returns to dfs(19)=>dfs(12)...can you explain that?

shivajikobardan
Check your indentation of the for loop. It is currently in line with the if block but you want to run it only if that condition is false right? Also it shouldn't stop at 1 completely but it will partially stop at 1.

I think it should go visited = [7,19,1,12,31...]

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/