DFS Depth First Search on Graph in DSA C++ - Execution Trace

Concept Flow - DFS Depth First Search on Graph

Start at source node

↓

Mark node as visited

↓

For each neighbor

↓

If neighbor not visited?

No→Skip

Yes↓

Recursively DFS on neighbor

↓

Backtrack when no unvisited neighbors

↓

All nodes reachable visited -> End

DFS starts at a node, marks it visited, then explores each unvisited neighbor deeply before backtracking.

Execution Sample

DSA C++

void dfs(int node) {
  visited[node] = true;
  for (int nbr : graph[node]) {
    if (!visited[nbr]) dfs(nbr);
  }
}

This code visits a node, marks it visited, then recursively visits all unvisited neighbors.

Execution Table

Step	Operation	Current Node	Visited Set	Stack (Call Trace)	Action	Graph State
1	Start DFS	0	{}	[0]	Mark 0 visited	Graph: 0->1,0->2,1->2,2->0,2->3,3->3
2	Visit neighbors of 0	0	{0}	[0]	Check neighbor 1	No change
3	Recurse DFS	1	{0}	[0,1]	Mark 1 visited	No change
4	Visit neighbors of 1	1	{0,1}	[0,1]	Check neighbor 2	No change
5	Recurse DFS	2	{0,1}	[0,1,2]	Mark 2 visited	No change
6	Visit neighbors of 2	2	{0,1,2}	[0,1,2]	Check neighbor 0 (visited)	Skip
7	Visit neighbors of 2	2	{0,1,2}	[0,1,2]	Check neighbor 3	No change
8	Recurse DFS	3	{0,1,2}	[0,1,2,3]	Mark 3 visited	No change
9	Visit neighbors of 3	3	{0,1,2,3}	[0,1,2,3]	Check neighbor 3 (visited)	Skip
10	Backtrack	3	{0,1,2,3}	[0,1,2]	No more neighbors	No change
11	Backtrack	2	{0,1,2,3}	[0,1]	No more neighbors	No change
12	Backtrack	1	{0,1,2,3}	[0]	No more neighbors	No change
13	Visit neighbors of 0	0	{0,1,2,3}	[0]	Check neighbor 2 (visited)	Skip
14	Backtrack	0	{0,1,2,3}	[]	No more neighbors, DFS complete	No change

💡 All reachable nodes visited, stack empty, DFS ends

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 8	Final
visited	{}	{0}	{0,1}	{0,1,2}	{0,1,2,3}	{0,1,2,3}
stack	[]	[0]	[0,1]	[0,1,2]	[0,1,2,3]	[]
current_node	N/A	0	1	2	3	N/A

Key Moments - 3 Insights

Why does DFS skip neighbor 0 when visiting node 2?

Because node 0 is already in the visited set (see step 6 in execution_table), DFS does not revisit it to avoid infinite loops.

Why does the stack grow and shrink during DFS?

The stack tracks the call trace of recursive DFS calls. It grows when DFS goes deeper (steps 3,5,8) and shrinks when backtracking (steps 10-14).

What happens when a node has no unvisited neighbors?

DFS backtracks by returning from the recursive call, removing the node from the stack (see steps 10-12).

Visual Quiz - 3 Questions

Look at the execution_table, what is the visited set after step 5?

A {0,1}

B {0,1,2}

C {0}

D {}

💡 Hint

Check the 'Visited Set' column at step 5 in execution_table.

At which step does DFS backtrack from node 3?

A Step 10

B Step 9

C Step 11

D Step 14

💡 Hint

Look for 'Backtrack' operation with current node 3 in execution_table.

If node 2 had an additional unvisited neighbor 4, what would happen at step 7?

A DFS would finish at node 2 immediately

B DFS would skip node 4

C DFS would recurse into node 4 before node 3

D DFS would backtrack to node 1

💡 Hint

DFS explores all unvisited neighbors recursively before backtracking (see steps 7-8).

Concept Snapshot

DFS (Depth First Search) explores graph nodes by going deep before backtracking.
Start at a node, mark visited, recursively visit unvisited neighbors.
Uses recursion stack to track path.
Avoids revisiting nodes to prevent loops.
Useful for connectivity, path finding, and cycle detection.

Full Transcript

DFS Depth First Search starts at a chosen node, marks it visited, then explores each neighbor deeply before backtracking. The recursive calls form a stack that grows when going deeper and shrinks when backtracking. Nodes already visited are skipped to avoid infinite loops. The execution table shows each step, current node, visited nodes, and stack state. Key moments include understanding why visited nodes are skipped, how the recursion stack changes, and what backtracking means. The visual quiz tests understanding of visited sets, backtracking steps, and how DFS would behave with additional neighbors.

Practice

1. What is the main idea behind Depth First Search (DFS) on a graph?

easy

A. Explore as far as possible along each branch before backtracking

B. Visit all neighbors of a node before moving deeper

C. Visit nodes in order of their distance from the start node

D. Randomly visit nodes without any order

Solution

1. Step 1: Understand DFS traversal

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

2. Step 2: Compare with other traversal methods

   BFS visits neighbors first, but DFS goes deep first, matching Explore as far as possible along each branch before backtracking.

3. Final Answer:

   Explore 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 neighbors first
• Assuming DFS visits nodes by distance

2. Which of the following is the correct C++ syntax to start a DFS from node 0 using recursion?

easy

A. DFS(visited, graph, 0);

B. dfs(0, visited, graph);

C. dfs(graph, 0, visited);

D. dfs(visited, 0, graph);

Solution

1. Step 1: Check typical DFS function signature

   Usually, DFS is called as dfs(node, visited, graph) where node is current node.

2. Step 2: Match the correct order

   dfs(0, visited, graph); matches the common order: dfs(0, visited, graph).

3. Final Answer:

   dfs(0, visited, graph); -> Option B

4. Quick Check:

   Call dfs with node first [OK]

Hint: DFS call starts with node, then visited, then graph [OK]

Common Mistakes:

• Swapping argument order
• Using uppercase DFS instead of dfs
• Passing graph before node

3. What will be the output order of nodes visited by DFS starting from node 0 in the graph below?

Graph adjacency list:
0: [1, 2]
1: [3]
2: []
3: []

Assuming DFS visits neighbors in ascending order.

medium

A. [0, 3, 1, 2]

B. [0, 2, 1, 3]

C. [0, 1, 3, 2]

D. [0, 1, 2, 3]

Solution

1. Step 1: Start DFS at node 0

   Visit 0, then explore neighbors in ascending order: 1, then 2.

2. Step 2: Explore neighbor 1

   From 1, visit 3 (only neighbor), then backtrack.

3. Step 3: Explore neighbor 2

   Node 2 has no neighbors, so visit and backtrack.

4. Final Answer:

   [0, 1, 3, 2] -> Option C

5. Quick Check:

   DFS order = 0,1,3,2 [OK]

Hint: Visit neighbors in order, go deep first [OK]

Common Mistakes:

• Visiting node 2 before node 1
• Not backtracking properly
• Confusing BFS order with DFS

4. Given the following DFS code snippet, what is the error?

void dfs(int node, vector<bool> &visited, vector &graph) {
  visited[node] = true;
  for (int i = 0; i < graph[node].size(); i++) {
    int neighbor = graph[node][i];
    if (visited[neighbor] = false) {
      dfs(neighbor, visited, graph);
    }
  }
}

medium

A. The function should return an int instead of void

B. The loop should use 'i <= graph[node].size()' instead of '<'

C. The visited vector should be passed by value, not reference

D. The condition 'if (visited[neighbor] = false)' uses assignment instead of comparison

Solution

1. Step 1: Check the if condition inside the loop

   The condition uses '=' which assigns false instead of comparing.

2. Step 2: Understand the impact of assignment in condition

   This causes the condition to always be false, so DFS won't recurse properly.

3. Final Answer:

   The condition 'if (visited[neighbor] = false)' uses assignment instead of comparison -> Option D

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Use '==' to compare, not '=' [OK]

Common Mistakes:

• Using '=' instead of '==' in conditions
• Loop boundary off-by-one errors
• Passing visited by value causing no effect

5. You have a graph with 5 nodes (0 to 4) and edges: 0-1, 0-2, 1-3, 1-4. Using DFS starting at node 0, how can you modify the algorithm to count the number of nodes reachable from node 0?

hard

A. Add a counter variable incremented each time a node is visited during DFS

B. Count nodes after DFS by checking which nodes have no neighbors

C. Use BFS instead of DFS to count nodes reachable

D. Count nodes by summing the degrees of all nodes

Solution

1. Step 1: Understand counting reachable nodes

   Counting nodes visited during DFS means incrementing a counter when marking a node visited.

2. Step 2: Why other options fail

   Counting nodes with no neighbors or summing degrees won't give reachable count; BFS is alternative but not required.

3. Final Answer:

   Add a counter variable incremented each time a node is visited during DFS -> Option A

4. Quick Check:

   Count nodes when visited in DFS [OK]

Hint: Increment count inside DFS when visiting nodes [OK]

Common Mistakes:

• Counting nodes with no neighbors instead of visited
• Using BFS unnecessarily
• Summing degrees instead of counting visited