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.