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

↓

All neighbors visited?

↓

Backtrack to previous node

↓

Done when all reachable nodes visited

Start from a node, mark it visited, then explore each unvisited neighbor deeply before backtracking.

Execution Sample

DSA C

void dfs(int node) {
  visited[node] = 1;
  for (int i = 0; i < graph[node].size(); i++) {
    int neighbor = graph[node][i];
    if (!visited[neighbor]) dfs(neighbor);
  }
}

This code visits nodes deeply in a graph using recursion, marking nodes visited to avoid repeats.

Execution Table

Step	Operation	Current Node	Visited Set	Call Stack	Action	Graph State
1	Start DFS	A	{}	[A]	Mark A visited	A: [B, C], B: [D], C: [E], D: [], E: []
2	Explore neighbor	A	{A}	[A, B]	B not visited, recurse	Same
3	Mark visited	B	{A}	[A, B]	Mark B visited	Same
4	Explore neighbor	B	{A, B}	[A, B, D]	D not visited, recurse	Same
5	Mark visited	D	{A, B}	[A, B, D]	Mark D visited	Same
6	Explore neighbors	D	{A, B, D}	[A, B, D]	No neighbors, backtrack	Same
7	Backtrack	B	{A, B, D}	[A, B]	Return to B	Same
8	All neighbors done	B	{A, B, D}	[A]	Backtrack to A	Same
9	Explore neighbor	A	{A, B, D}	[A, C]	C not visited, recurse	Same
10	Mark visited	C	{A, B, D}	[A, C]	Mark C visited	Same
11	Explore neighbor	C	{A, B, D, C}	[A, C, E]	E not visited, recurse	Same
12	Mark visited	E	{A, B, D, C}	[A, C, E]	Mark E visited	Same
13	Explore neighbors	E	{A, B, D, C, E}	[A, C, E]	No neighbors, backtrack	Same
14	Backtrack	C	{A, B, D, C, E}	[A, C]	Return to C	Same
15	All neighbors done	C	{A, B, D, C, E}	[A]	Backtrack to A	Same
16	All neighbors done	A	{A, B, D, C, E}	[]	DFS complete	Same

💡 All reachable nodes visited, call stack empty, DFS ends

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 9	After Step 12	Final
visited	{}	{A}	{A, B}	{A, B, D}	{A, B, D}	{A, B, D, C, E}	{A, B, D, C, E}
call_stack	[]	[A]	[A, B]	[A, B, D]	[A, C]	[A, C, E]	[]

Key Moments - 3 Insights

Why do we mark a node visited before exploring its neighbors?

Marking visited early (see Step 1 and Step 3) prevents revisiting the same node and infinite loops, as shown in the visited set updates in the execution_table.

Why does DFS backtrack when a node has no unvisited neighbors?

When no neighbors are left (Step 6 and Step 13), DFS returns to the previous node to explore other paths, shown by the call stack shrinking in the execution_table.

How does the call stack represent the current path in DFS?

The call stack (variable_tracker) shows nodes currently being explored; pushing when recursing deeper and popping when backtracking, matching the execution_table's Call Stack column.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, which nodes are marked visited?

A {A}

B {A, B, D}

C {A, B}

D {}

💡 Hint

Check the Visited Set column at Step 5 in the execution_table.

At which step does DFS start exploring node C?

A Step 9

B Step 7

C Step 12

D Step 3

💡 Hint

Look at the Current Node and Operation columns in the execution_table.

If node E had a neighbor F not visited, what would happen at Step 12?

A DFS would backtrack immediately

B Node E would be skipped

C DFS would recurse into F, adding it to the call stack

D DFS would restart from node A

💡 Hint

Refer to the recursion behavior shown in Steps 2-5 in the execution_table.

Concept Snapshot

DFS explores graph nodes deeply by:
- Starting at a node, marking it visited
- Recursively visiting unvisited neighbors
- Using a call stack to track path
- Backtracking when no neighbors left
- Ends when all reachable nodes visited

Full Transcript

Depth First Search (DFS) starts at a chosen node, marks it visited to avoid repeats, then explores each neighbor deeply before backtracking. The call stack tracks the current path. When a node has no unvisited neighbors, DFS backtracks to explore other paths. This continues until all reachable nodes are visited. The visited set prevents cycles and repeated visits. The execution table shows each step's current node, visited nodes, call stack, and actions taken, illustrating the recursive nature of DFS.