DFS Depth First Search on Graph in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of DFS traversal on a simple graph

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

DSA Typescript

const graph = new Map<number, number[]>([
  [0, [1, 2]],
  [1, [3]],
  [2, []],
  [3, []]
]);

function dfs(node: number, visited: Set<number>, graph: Map<number, number[]>, result: number[]) {
  visited.add(node);
  result.push(node);
  for (const neighbor of graph.get(node) || []) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, visited, graph, result);
    }
  }
}

const visited = new Set<number>();
const result: number[] = [];
dfs(0, visited, graph, result);
console.log(result.join(' -> ') + ' -> null');

A 0 -> 2 -> 1 -> 3 -> null

B 0 -> 1 -> 3 -> 2 -> null

C 0 -> 1 -> 2 -> 3 -> null

D 0 -> 3 -> 1 -> 2 -> null

💡 Hint

Remember DFS explores as far as possible along each branch before backtracking.

The DFS starts at node 0, visits 1 first (the first neighbor), then goes deeper to 3. After finishing 3, it backtracks and visits 2.

🧠 Conceptual

intermediate

Number of nodes visited in DFS

Given the graph below, how many nodes will DFS visit starting from node 2?

DSA Typescript

const graph = new Map<number, number[]>([
  [0, [1]],
  [1, [2]],
  [2, [3]],
  [3, []],
  [4, [0]]
]);

A 2

B 4

C 1

D 3

💡 Hint

DFS visits all reachable nodes from the start node.

Starting at node 2, DFS visits 2, then 3. Node 3 has no neighbors. So nodes visited are 2 and 3. But node 2 also connects to 3 only, so total 2 nodes visited.

However, check carefully: Node 2 connects to 3 only, so nodes visited are 2 and 3 only, total 2 nodes.

❓ Predict Output

advanced

DFS traversal order with cycle in graph

What is the output of the DFS traversal starting from node 0 in the graph with a cycle?

DSA Typescript

const graph = new Map<number, number[]>([
  [0, [1]],
  [1, [2]],
  [2, [0, 3]],
  [3, []]
]);

function dfs(node: number, visited: Set<number>, graph: Map<number, number[]>, result: number[]) {
  visited.add(node);
  result.push(node);
  for (const neighbor of graph.get(node) || []) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, visited, graph, result);
    }
  }
}

const visited = new Set<number>();
const result: number[] = [];
dfs(0, visited, graph, result);
console.log(result.join(' -> ') + ' -> null');

A 0 -> 2 -> 1 -> 3 -> null

B 0 -> 1 -> 3 -> 2 -> null

C 0 -> 1 -> 2 -> 3 -> null

D 0 -> 3 -> 2 -> 1 -> null

💡 Hint

DFS avoids revisiting nodes already visited to prevent infinite loops.

DFS starts at 0, visits 1, then 2. From 2, it tries to visit 0 but 0 is already visited, so it skips. Then it visits 3.

🔧 Debug

advanced

Identify the error in DFS implementation

What error will the following DFS code produce when run on the given graph?

DSA Typescript

const graph = new Map<number, number[]>([
  [0, [1]],
  [1, [2]],
  [2, []]
]);

function dfs(node: number, visited: Set<number>, graph: Map<number, number[]>, result: number[]) {
  if (visited.has(node)) return;
  result.push(node);
  for (const neighbor of graph.get(node)!) {
    dfs(neighbor, visited, graph, result);
  }
}

const visited = new Set<number>();
const result: number[] = [];
dfs(0, visited, graph, result);
console.log(result.join(' -> ') + ' -> null');

A Runtime error: Maximum call stack size exceeded

B The code runs correctly and outputs '0 -> 1 -> 2 -> null'

C TypeError: Cannot read property 'Symbol.iterator' of undefined

D The output is '0 -> 1 -> null'

💡 Hint

Check if the visited set is updated properly to avoid infinite recursion.

Although the visited set is never updated (missing visited.add(node)), this graph is acyclic with no back edges, so no node is revisited. The recursion terminates normally, producing output '0 -> 1 -> 2 -> null'. In graphs with cycles, it would cause stack overflow.

🚀 Application

expert

DFS to find all connected components count

Given the graph below, what is the number of connected components?

DSA Typescript

const graph = new Map<number, number[]>([
  [0, [1]],
  [1, [0]],
  [2, [3]],
  [3, [2]],
  [4, []]
]);

function dfs(node: number, visited: Set<number>, graph: Map<number, number[]>) {
  visited.add(node);
  for (const neighbor of graph.get(node) || []) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, visited, graph);
    }
  }
}

const visited = new Set<number>();
let count = 0;
for (const node of graph.keys()) {
  if (!visited.has(node)) {
    dfs(node, visited, graph);
    count++;
  }
}
console.log(count);

A 3

B 2

C 1

D 4

💡 Hint

Each connected component is a group of nodes reachable from each other.

Nodes 0 and 1 form one component, nodes 2 and 3 form another, and node 4 alone is the third component.

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 until all are visited

Solution

1. Step 1: Understand DFS traversal strategy

   DFS explores nodes 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 goes deep first, BFS goes wide first [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 TypeScript function signature for a DFS function on a graph represented as an adjacency list?

easy

A. function dfs(graph: Map, start: number): void

B. function dfs(graph: number[], start: number): void

C. function dfs(graph: number[][], start: number): void

D. function dfs(graph: string[][], start: string): void

Solution

1. Step 1: Identify graph representation type

   An adjacency list for a graph with numbered nodes is usually number[][], where each index holds neighbors.

2. Step 2: Check parameter types

   Start node is a number, so function signature with graph: number[][] and start: number is correct.

3. Final Answer:

   function dfs(graph: number[][], start: number): void -> Option C

4. Quick Check:

   Adjacency list = number[][], start node = number [OK]

Hint: Adjacency list uses array of arrays for neighbors [OK]

Common Mistakes:

• Using number[] instead of number[][] for adjacency list
• Using Map with incorrect value type
• Using string types for numeric graphs

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

const graph = [[1, 2], [2], [0, 3], [3]];
const visited: boolean[] = [];
const result: number[] = [];
function dfs(node: number) {
  if (visited[node]) return;
  visited[node] = true;
  result.push(node);
  for (const neighbor of graph[node]) {
    dfs(neighbor);
  }
}
dfs(0);
console.log(result);

medium

A. [0, 2, 3, 1]

B. [0, 2, 1, 3]

C. [0, 1, 2]

D. [0, 1, 2, 3]

Solution

1. Step 1: Start DFS at node 0

   Visit 0, mark visited, add to result: [0]. Neighbors: 1, 2.

2. Step 2: Visit neighbor 1

   Visit 1, mark visited, add: [0,1]. Neighbor: 2.

3. Step 3: Visit neighbor 2 from 1

   Visit 2, mark visited, add: [0,1,2]. Neighbors: 0 (visited), 3.

4. Step 4: Visit neighbor 3 from 2

   Visit 3, mark visited, add: [0,1,2,3]. Neighbor: 3 (already visited).

5. Final Answer:

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

6. Quick Check:

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

Hint: Follow neighbors recursively, mark visited to avoid repeats [OK]

Common Mistakes:

• Not marking nodes visited before recursion
• Visiting neighbors in wrong order
• Ignoring already visited nodes

4. Identify the bug in this DFS implementation and choose the fix:

function dfs(node: number, graph: number[][], visited: boolean[]) {
  visited[node] = true;
  for (const neighbor of graph[node]) {
    if (!visited[neighbor]) {
      dfs(neighbor, graph, visited);
    }
  }
}

const graph = [[1], [2], [0]];
const visited = new Array(graph.length).fill(false);
dfs(0, graph, visited);
console.log(visited);

medium

A. Mark visited[node] = true after recursive calls

B. Initialize visited array with true instead of false

C. Add a base case to return if node is already visited at start

D. No bug, code works correctly

Solution

1. Step 1: Check visited marking timing

   Visited[node] is marked true before recursion, preventing revisits.

2. Step 2: Verify recursion and base case

   Recursion only happens if neighbor not visited, so no infinite loops.

3. Final Answer:

   No bug, code works correctly -> Option D

4. Quick Check:

   Visited marked before recursion = correct DFS [OK]

Hint: Mark visited before recursion to avoid cycles [OK]

Common Mistakes:

• Marking visited after recursion causing infinite loops
• Initializing visited array incorrectly
• Missing base case check

5. Given a graph with possible cycles, how can you modify DFS to detect if a cycle exists starting from a given node? Choose the best approach.

hard

A. Use a recursion stack array to track nodes in the current path and detect back edges

B. Only mark nodes visited after all neighbors are visited

C. Use BFS instead of DFS to detect cycles

D. Ignore visited nodes and continue traversal

Solution

1. Step 1: Understand cycle detection in DFS

   Detecting cycles requires knowing if a node is in the current recursion path (stack).

2. Step 2: Use recursion stack tracking

   Maintain a separate array to track nodes currently in recursion; if a neighbor is in this stack, a cycle exists.

3. Step 3: Evaluate other options

   Marking visited after neighbors or using BFS won't reliably detect cycles; ignoring visited nodes causes infinite loops.

4. Final Answer:

   Use a recursion stack array to track nodes in the current path and detect back edges -> Option A

5. Quick Check:

   Cycle detection = recursion stack tracking [OK]

Hint: Track recursion path to find back edges indicating cycles [OK]

Common Mistakes:

• Not tracking recursion stack causing missed cycles
• Using BFS which doesn't track recursion path
• Marking visited too late or ignoring visited nodes