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

Concept Flow - DFS Depth First Search on Graph

Start at initial node

↓

Mark node as visited

↓

Explore each unvisited neighbor

↓

For each neighbor: DFS recursively

↓

Backtrack when no unvisited neighbors

↓

All nodes visited or reachable nodes done

↓

End DFS

Start from a node, mark it visited, explore neighbors deeply before backtracking, repeat until all reachable nodes are visited.

Execution Sample

DSA Javascript

const graph = {
  A: ['B', 'C'],
  B: ['D'],
  C: ['E'],
  D: [],
  E: []
};

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

This code performs DFS starting from node 'A' on a simple graph, visiting nodes deeply before backtracking.

Execution Table

Step	Operation	Current Node	Visited Set	Stack (Call Path)	Action Taken
1	Start DFS	A	{}	[]	Visit A, add to visited, push neighbors B, C
2	Visit neighbor	B	{A}	[A]	Visit B, add to visited, push neighbor D
3	Visit neighbor	D	{A, B}	[A, B]	Visit D, add to visited, no neighbors
4	Backtrack	B	{A, B, D}	[A]	All neighbors visited, backtrack to A
5	Visit neighbor	C	{A, B, D}	[A]	Visit C, add to visited, push neighbor E
6	Visit neighbor	E	{A, B, C, D}	[A, C]	Visit E, add to visited, no neighbors
7	Backtrack	C	{A, B, C, D, E}	[A]	All neighbors visited, backtrack to A
8	Backtrack	A	{A, B, C, D, E}	[]	All neighbors visited, DFS complete

💡 All reachable nodes visited, recursion unwinds fully, 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	Final
visited	{}	{A}	{A, B}	{A, B, D}	{A, B, D}	{A, B, C, D}	{A, B, C, D, E}	{A, B, C, D, E}	{A, B, C, D, E}
stack (call path)	[]	[A]	[A, B]	[A, B]	[A]	[A, C]	[A, C]	[A]	[]
current node	null	A	B	D	B	C	E	C	A

Key Moments - 3 Insights

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

Marking a node as visited before exploring neighbors prevents revisiting the same node and avoids infinite loops, as shown in Step 1 where 'A' is added to visited before going deeper.

Why do we backtrack after visiting all neighbors?

Backtracking happens when a node has no unvisited neighbors left, so the recursion returns to the previous node to explore other paths, as seen in Steps 4 and 7.

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

The stack shows the nodes currently being explored in the recursion path, growing when going deeper and shrinking when backtracking, visible in the 'Stack (Call Path)' column.

Visual Quiz - 3 Questions

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

A {A, B, D}

B {A, B}

C {A, B, C}

D {A, B, C, D}

💡 Hint

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

At which step does the DFS first backtrack from node 'B'?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for 'Backtrack' operations and the current node in the execution table.

If node 'E' had an additional neighbor 'F', how would the visited set change after Step 6?

A {A, B, C, D, E, F}

B {A, B, C, D}

C {A, B, C, D, E}

D {A, B, C, D, F}

💡 Hint

Since 'F' is a neighbor of 'E', it would be visited after Step 6, but currently it is not in the graph.

Concept Snapshot

DFS (Depth First Search) explores graph nodes deeply before backtracking.
Start at a node, mark visited, recursively visit unvisited neighbors.
Uses recursion or stack to track path.
Prevents cycles by marking visited nodes.
Backtracks when no unvisited neighbors remain.
Useful for path finding, connectivity checks.

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 or a stack to remember the path. Each node is marked visited before exploring neighbors to avoid revisiting and infinite loops. When a node has no unvisited neighbors, DFS backtracks to the previous node to explore other paths. This continues until all reachable nodes are visited. The execution table shows each step, current node, visited nodes, and the call stack representing the path. Key moments include understanding why nodes are marked visited early, why backtracking happens, and how the call stack tracks the current path. DFS is useful for exploring graphs, finding paths, and checking connectivity.

Practice

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

easy

A. It only visits nodes connected directly to the start node.

B. It visits nodes level by level from the start node.

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

D. It randomly visits nodes without any order.

Solution

1. Step 1: Understand DFS traversal

   DFS explores a path deeply before moving to another path.

2. Step 2: Compare with other traversals

   BFS visits nodes level by level, but DFS goes deep first.

3. Final Answer:

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

4. Quick Check:

   DFS = deep exploration first [OK]

Hint: DFS goes deep first, BFS goes wide first [OK]

Common Mistakes:

• Confusing DFS with BFS
• Thinking DFS visits nodes randomly
• Assuming DFS only visits direct neighbors

2. Which of the following is the correct way to start a DFS function in JavaScript for a graph represented as adjacency list graph?

easy

A. function dfs(node, visited = new Set()) {

B. function dfs(node, visited = []) {

C. function dfs(node, visited = {}) {

D. function dfs(node, visited = 0) {

Solution

1. Step 1: Identify suitable data structure for visited nodes

   A Set is ideal to track visited nodes efficiently.

2. Step 2: Check function signature correctness

   Using visited = new Set() initializes visited nodes properly.

3. Final Answer:

   function dfs(node, visited = new Set()) { -> Option A

4. Quick Check:

   Use Set for visited nodes [OK]

Hint: Use Set to track visited nodes in DFS [OK]

Common Mistakes:

• Using array or object incorrectly for visited
• Initializing visited as a number
• Not initializing visited parameter

3. Given the graph adjacency list:

const graph = {
  1: [2, 3],
  2: [4],
  3: [],
  4: []
};

function dfs(node, visited = new Set()) {
  visited.add(node);
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, visited);
    }
  }
  return Array.from(visited);
}

console.log(dfs(1));

What is the output?

medium

A. [1, 3, 2, 4]

B. [1, 4, 2, 3]

C. [1, 2, 3, 4]

D. [1, 2, 4, 3]

Solution

1. Step 1: Start DFS from node 1

   Visit 1, then neighbors 2 and 3 in order.

2. Step 2: Visit neighbors recursively

   From 2, visit 4. From 3, no neighbors. Order: 1, 2, 4, 3.

3. Final Answer:

   [1, 2, 4, 3] -> Option D

4. Quick Check:

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

Hint: Follow neighbors deeply before next sibling [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Confusing BFS order with DFS
• Not converting Set to array properly

4. Find the error in this DFS code snippet for graph traversal:

const graph = {
  1: [2, 3],
  2: [4],
  3: [],
  4: []
};

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

console.log(Array.from(dfs(1)));

medium

A. The condition should be if (!visited.has(neighbor)) instead of if (visited.has(neighbor))

B. The visited set should be an array instead

C. The graph object keys should be strings, not numbers

D. The function should return an array, not a set

Solution

1. Step 1: Check the neighbor visit condition

   It incorrectly calls dfs if neighbor is already visited, causing infinite recursion.

2. Step 2: Correct the condition

   Change to if (!visited.has(neighbor)) to visit unvisited neighbors only.

3. Final Answer:

   The condition should be if (!visited.has(neighbor)) instead of if (visited.has(neighbor)) -> Option A

4. Quick Check:

   Visit only unvisited neighbors [OK]

Hint: Call DFS only if neighbor not visited [OK]

Common Mistakes:

• Calling DFS on already visited nodes
• Using wrong data structure for visited
• Returning wrong type from DFS

5. You want to find if there is a path from node 1 to node 5 in this graph:

const graph = {
  1: [2, 3],
  2: [4],
  3: [5],
  4: [],
  5: []
};

function dfs(node, target, visited = new Set()) {
  if (node === target) return true;
  visited.add(node);
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      if (dfs(neighbor, target, visited)) return true;
    }
  }
  return false;
}

console.log(dfs(1, 5));

What will be the output and why?

hard

A. false, because the visited set is not updated correctly

B. true, because DFS finds a path 1 -> 3 -> 5

C. true, because DFS visits all nodes regardless of target

D. false, because node 5 is not directly connected to 1

Solution

1. Step 1: Check DFS path search logic

   DFS returns true immediately when target node is found.

2. Step 2: Trace path from 1 to 5

   Path exists: 1 -> 3 -> 5, so DFS returns true.

3. Final Answer:

   true, because DFS finds a path 1 -> 3 -> 5 -> Option B

4. Quick Check:

   DFS finds path = true [OK]

Hint: DFS returns true when target found [OK]

Common Mistakes:

• Assuming direct connection needed
• Ignoring early return on target found
• Not updating visited set properly