DFS Depth First Search on Graph in DSA Python - Execution Trace

Concept Flow - DFS Depth First Search on Graph

Start at a node

↓

Mark node as visited

↓

For each neighbor

↓

If neighbor not visited?

No→Skip

Yes↓

Recursively DFS on neighbor

↓

All neighbors visited?

↓

Backtrack to previous node

↓

Done when all reachable nodes visited

Start from a node, mark it visited, then recursively visit each unvisited neighbor, backtracking when no neighbors remain.

Execution Sample

DSA Python

graph = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['E'],
  'D': [],
  'E': []
}
visited = set()
def dfs(node):
  visited.add(node)
  for n in graph[node]:
    if n not in visited:
      dfs(n)

# Start DFS from 'A'
dfs('A')

This code performs DFS starting at node 'A', visiting nodes deeply before backtracking.

Execution Table

Step	Operation	Current Node	Visited Set	Call Stack	Action	Visual State
1	Start DFS	A	{}	['A']	Visit A	A(visited)
2	Explore neighbor	A	{A}	['A', 'B']	Visit B	A(visited) -> B(visited)
3	Explore neighbor	B	{A, B}	['A', 'B', 'D']	Visit D	A(visited) -> B(visited) -> D(visited)
4	No neighbors	D	{A, B, D}	['A', 'B']	Backtrack from D	A(visited) -> B(visited) -> D(visited)
5	No more neighbors of B	B	{A, B, D}	['A']	Backtrack from B	A(visited) -> B(visited) -> D(visited)
6	Explore next neighbor	A	{A, B, D}	['A', 'C']	Visit C	A(visited) -> B(visited) -> D(visited) -> C(visited)
7	Explore neighbor	C	{A, B, D, C}	['A', 'C', 'E']	Visit E	A(visited) -> B(visited) -> D(visited) -> C(visited) -> E(visited)
8	No neighbors	E	{A, B, D, C, E}	['A', 'C']	Backtrack from E	A(visited) -> B(visited) -> D(visited) -> C(visited) -> E(visited)
9	No more neighbors of C	C	{A, B, D, C, E}	['A']	Backtrack from C	A(visited) -> B(visited) -> D(visited) -> C(visited) -> E(visited)
10	No more neighbors of A	A	{A, B, D, C, E}	[]	DFS complete	A(visited) -> B(visited) -> D(visited) -> C(visited) -> E(visited)

💡 All reachable nodes from 'A' visited, call stack empty, DFS ends

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
visited	{}	{'A'}	{'A', 'B'}	{'A', 'B', 'D'}	{'A', 'B', 'D'}	{'A', 'B', 'D'}	{'A', 'B', 'D', 'C'}	{'A', 'B', 'D', 'C', 'E'}	{'A', 'B', 'D', 'C', 'E'}	{'A', 'B', 'D', 'C', 'E'}	{'A', 'B', 'D', 'C', 'E'}
call_stack	[]	['A']	['A', 'B']	['A', 'B', 'D']	['A', 'B']	['A']	['A', 'C']	['A', 'C', 'E']	['A', 'C']	['A']	[]

Key Moments - 3 Insights

Why do we add a node to 'visited' before exploring its neighbors?

Adding the node to 'visited' immediately (see Step 1) prevents revisiting it later and avoids infinite loops in cyclic graphs.

Why does the call stack shrink after visiting nodes with no neighbors?

When a node has no unvisited neighbors (Step 4 and Step 8), DFS backtracks by popping the node from the call stack, moving back to explore other neighbors.

Why does DFS visit nodes deeply before visiting siblings?

DFS explores one neighbor fully before moving to the next (see Steps 2-5), which is why it goes deep into the graph before backtracking.

Visual Quiz - 3 Questions

Look at the execution table at Step 3, what nodes are in the 'visited' set?

A {'A', 'B'}

B {'A', 'B', 'D'}

C {'A', 'B', 'C'}

D {'A', 'B', 'D', 'C'}

💡 Hint

Check the 'Visited Set' column in Step 3 of the execution table.

At which step does the DFS backtrack from node 'E'?

A Step 8

B Step 9

C Step 7

D Step 10

💡 Hint

Look at the 'Action' column for backtracking from 'E' in the execution table.

If node 'C' had an additional neighbor 'F' not visited yet, at which step would 'F' be added to the call stack?

A After Step 6

B After Step 8

C After Step 7

D After Step 9

💡 Hint

Neighbors are explored immediately after visiting a node, see how 'E' was added after 'C' at Step 7.

Concept Snapshot

DFS (Depth First Search) explores graph nodes deeply before backtracking.
Start at a node, mark visited, recursively visit unvisited neighbors.
Uses call stack to track path.
Prevents cycles by tracking visited nodes.
Ends when all reachable nodes are visited.

Full Transcript

Depth First Search (DFS) starts at a chosen node and marks it visited immediately to avoid revisiting. It then explores each neighbor deeply by recursively calling DFS on unvisited neighbors. The call stack keeps track of the path, allowing backtracking when a node has no unvisited neighbors. This process continues until all reachable nodes from the start node are visited. The visited set prevents cycles and repeated visits. The execution table shows each step, the current node, visited nodes, call stack state, and actions taken, illustrating how DFS traverses the graph deeply before backtracking.

Practice

1. What does DFS (Depth First Search) do when exploring a graph?

easy

A. It explores as far as possible along each branch before backtracking.

B. It explores all neighbors at the current depth before going deeper.

C. It visits nodes randomly without any order.

D. It only visits nodes with the highest value first.

Solution

1. Step 1: Understand DFS traversal

   DFS explores a graph by going deep into one branch before backtracking to explore others.

2. Step 2: Compare with other traversal methods

   BFS explores neighbors level by level, but DFS goes deep first.

3. Final Answer:

   It explores as far as possible along each branch before backtracking. -> Option A

4. Quick Check:

   DFS = deep exploration first [OK]

Hint: DFS means go deep first, then backtrack [OK]

Common Mistakes:

• Confusing DFS with BFS
• Thinking DFS visits nodes randomly
• Assuming DFS visits nodes by value

2. Which of the following is the correct Python syntax to start a DFS function on a graph represented as adjacency list graph from node start?

easy

A. def dfs(start, graph):

B. def dfs(graph, start):

C. def dfs(graph):

D. def dfs(start):

Solution

1. Step 1: Identify required parameters for DFS

   DFS needs the graph and the starting node to begin traversal.

2. Step 2: Check function signature correctness

   def dfs(graph, start): correctly defines a function with parameters (graph, start).

3. Final Answer:

   def dfs(graph, start): -> Option B

4. Quick Check:

   DFS needs graph and start node [OK]

Hint: DFS function needs graph and start node parameters [OK]

Common Mistakes:

• Swapping parameter order incorrectly
• Missing one of the parameters
• Using only one parameter when two are needed

3. What is the output of the following DFS traversal starting from node 0?

graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}
visited = set()
def dfs(node):
    if node not in visited:
        print(node, end=' ')
        visited.add(node)
        for neighbor in graph[node]:
            dfs(neighbor)
dfs(0)

medium

A. 0 3 2 1

B. 0 2 3 1

C. 0 1 3 2

D. 0 1 2 3

Solution

1. Step 1: Start DFS from node 0

   Visit 0, mark visited. Neighbors: 1, 2.

2. Step 2: Visit neighbor 1

   Visit 1, mark visited. Neighbor: 2.

3. Step 3: Visit neighbor 2

   Visit 2, mark visited. Neighbors: 0 (visited), 3.

4. Step 4: Visit neighbor 3

   Visit 3, mark visited. Neighbor: 3 (already visited).

5. Final Answer:

   0 1 2 3 -> Option D

6. Quick Check:

   DFS order = 0 1 2 3 [OK]

Hint: Follow neighbors depth-first, avoid revisiting nodes [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Revisiting already visited nodes
• Confusing BFS order with DFS

4. Find the error in this DFS code snippet and select the fix:

graph = {0: [1], 1: [2], 2: []}
visited = set()
def dfs(node):
    if node in visited:
        return
    print(node)
    for neighbor in graph[node]:
        dfs(neighbor)
dfs(0)

medium

A. Add 'visited.add(node)' after printing node to mark it visited.

B. Change 'if node in visited' to 'if node not in visited'.

C. Remove the 'return' statement inside the if condition.

D. Add 'visited.remove(node)' after recursive calls.

Solution

1. Step 1: Identify missing visited marking

   The code never adds nodes to visited, so it revisits nodes infinitely.

2. Step 2: Fix by adding visited marking

   Adding 'visited.add(node)' after printing marks node as visited to avoid revisits.

3. Final Answer:

   Add 'visited.add(node)' after printing node to mark it visited. -> Option A

4. Quick Check:

   Mark visited after visiting node [OK]

Hint: Always add node to visited set after visiting [OK]

Common Mistakes:

• Forgetting to mark nodes visited
• Incorrect if condition logic
• Removing nodes from visited incorrectly

5. Given a directed graph represented as adjacency list:

graph = {0: [1, 2], 1: [2], 2: [3], 3: [1]}

Write the DFS traversal order starting from node 0 that detects cycles by tracking recursion stack. What is the order of nodes visited before detecting a cycle?

hard

A. 0 1 2

B. 0 2 3 1

C. 0 1 2 3

D. 0 2 1 3

Solution

1. Step 1: Start DFS from node 0 and track recursion stack

   Visit 0, then 1, then 2, then 3. At 3, neighbor 1 is in recursion stack, cycle detected.

2. Step 2: List nodes visited before cycle detection

   Nodes visited in order: 0, 1, 2, 3 before cycle found.

3. Final Answer:

   0 1 2 3 -> Option C

4. Quick Check:

   DFS with cycle detection visits 0 1 2 3 [OK]

Hint: Track recursion stack to detect cycles during DFS [OK]

Common Mistakes:

• Ignoring recursion stack for cycle detection
• Stopping traversal too early
• Visiting nodes in wrong order