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

Concept Flow - DFS Depth First Search on Graph

Start at root node

↓

Mark node as visited

↓

Explore first unvisited neighbor

↓

Recursive DFS call on neighbor

↓

All neighbors visited?

No→Repeat for next neighbor

Yes↓

Backtrack to previous node

↓

All nodes visited?

No→Continue

Yes↓

End

Start from a node, visit it, then recursively visit each unvisited neighbor deeply before backtracking.

Execution Sample

DSA Typescript

function dfs(node, visited) {
  visited.add(node);
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) dfs(neighbor, visited);
  }
}

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 Taken	Graph State
1	Start DFS	A	{}	[]	Visit A	A: [B, C], B: [D], C: [E], D: [], E: []
2	Visit Node	A	{A}	[A]	Mark A visited	Same
3	Explore neighbor	A	{A}	[A]	Check neighbor B	Same
4	Visit Node	B	{A}	[A, B]	Mark B visited	Same
5	Explore neighbor	B	{A, B}	[A, B]	Check neighbor D	Same
6	Visit Node	D	{A, B}	[A, B, D]	Mark D visited	Same
7	Explore neighbor	D	{A, B, D}	[A, B, D]	No neighbors to visit	Same
8	Backtrack	D	{A, B, D}	[A, B]	Return to B	Same
9	All neighbors visited?	B	{A, B, D}	[A, B]	Yes, backtrack	Same
10	Backtrack	B	{A, B, D}	[A]	Return to A	Same
11	Explore neighbor	A	{A, B, D}	[A]	Check neighbor C	Same
12	Visit Node	C	{A, B, D}	[A, C]	Mark C visited	Same
13	Explore neighbor	C	{A, B, D, C}	[A, C]	Check neighbor E	Same
14	Visit Node	E	{A, B, D, C}	[A, C, E]	Mark E visited	Same
15	Explore neighbor	E	{A, B, D, C, E}	[A, C, E]	No neighbors to visit	Same
16	Backtrack	E	{A, B, D, C, E}	[A, C]	Return to C	Same
17	All neighbors visited?	C	{A, B, D, C, E}	[A, C]	Yes, backtrack	Same
18	Backtrack	C	{A, B, D, C, E}	[A]	Return to A	Same
19	All neighbors visited?	A	{A, B, D, C, E}	[A]	Yes, DFS complete	Same
20	End DFS	-	{A, B, D, C, E}	[]	All nodes visited	Same

💡 All nodes visited, no unvisited neighbors remain, DFS ends

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 12	After Step 14	Final
visited	{}	{A}	{A, B}	{A, B, D}	{A, B, D, C}	{A, B, D, C, E}	{A, B, D, C, E}
stack	[]	[A]	[A, B]	[A, B, D]	[A, C]	[A, C, E]	[]
current_node	-	A	B	D	C	E	-

Key Moments - 3 Insights

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

Marking a node visited early (see Step 2) prevents revisiting it during neighbor checks (Step 3), avoiding infinite loops.

Why do we backtrack after visiting all neighbors?

Backtracking (Steps 8, 10, 16, 18) happens when no unvisited neighbors remain, so DFS returns to previous nodes to explore other paths.

Why does the stack grow and shrink during DFS?

The stack (call trace) grows when DFS goes deeper (Steps 4, 6, 12, 14) and shrinks when backtracking (Steps 8, 10, 16, 18), reflecting recursion depth.

Visual Quiz - 3 Questions

Look at the execution table, what is the visited set after Step 6?

A {A, B}

B {A, B, D}

C {A, B, C}

D {A, B, D, C}

💡 Hint

Check the 'Visited Set' column at Step 6 in the execution table.

At which step does DFS first backtrack from node D?

A Step 8

B Step 7

C Step 9

D Step 10

💡 Hint

Look for 'Backtrack' operation with current node D in the execution table.

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

A DFS would skip F and finish

B DFS would backtrack immediately

C DFS would visit F next, stack grows

D DFS would restart from A

💡 Hint

At Step 15, DFS explores neighbors; unvisited neighbors cause recursive calls and stack growth.

Concept Snapshot

DFS visits nodes deeply before backtracking.
Start at a node, mark visited.
Recursively visit unvisited neighbors.
Use stack (call trace) to track path.
Backtrack when no neighbors left.
Ends when all reachable nodes visited.

Full Transcript

Depth First Search (DFS) starts at a chosen node, marks it visited, then explores each neighbor deeply before backtracking. The process uses recursion, which acts like a stack to remember the path. Each step marks nodes visited to avoid repeats. When a node has no unvisited neighbors, DFS backtracks to explore other paths. This continues until all nodes reachable from the start are visited. The execution table shows each step, the current node, visited nodes, and the call stack. Key moments include marking visited early to prevent loops, backtracking when no neighbors remain, and stack changes reflecting recursion depth.