Data Structure DFS Practice Questions with Solutions

By /

Introductions

Depth-First Search (DFS) is a graph traversal technique that explores one path as deeply as possible before returning and exploring another path. DFS can be implemented using recursion or a stack. In this chapter, you will practice DFS through 10 solved JavaScript questions covering recursive traversal, iterative DFS, path exploration, cycle detection, connected components, and grid-based problems. Each question focuses on a different practical use of DFS. Data Structure DFS practice questions with solutions help to build concepts.

Question 1: Perform Recursive DFS Traversal

Question

Given the following graph, perform DFS starting from vertex A.

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

Solution

DFS can be implemented using recursion.

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

function dfs(graph, vertex, visited = new Set()) {
  if (visited.has(vertex)) {
    return;
  }

  visited.add(vertex);
  console.log(vertex);

  for (const neighbor of graph[vertex]) {
    dfs(graph, neighbor, visited);
  }
}

dfs(graph, "A");

Output

A
B
D
C
E

Answer

The DFS traversal is:

A → B → D → C → E

DFS completely explores the A → B → D path before moving to C.

Question 2: Implement DFS Using a Stack

Question

Perform DFS without recursion using a stack.

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

Solution

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

function dfs(graph, start) {
  const stack = [start];
  const visited = new Set();
  const result = [];

  while (stack.length > 0) {
    const vertex = stack.pop();

    if (visited.has(vertex)) {
      continue;
    }

    visited.add(vertex);
    result.push(vertex);

    for (const neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }

  return result;
}

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

Output

[ 1, 3, 5, 2, 4 ]

Answer

The exact DFS order depends on the order in which neighbors are pushed onto the stack.

Here, the traversal is:

1 → 3 → 5 → 2 → 4

Question 3: Find Whether a Path Exists Using DFS

Question

Use DFS to determine whether a path exists from A to F.

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

Solution

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

function hasPath(graph, start, target, visited = new Set()) {
  if (start === target) {
    return true;
  }

  visited.add(start);

  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      if (hasPath(graph, neighbor, target, visited)) {
        return true;
      }
    }
  }

  return false;
}

console.log(hasPath(graph, "A", "F"));

Output

true

Answer

A path exists:

A → B → D → E → F

Therefore, DFS returns true.

Question 4: Find the Actual Path Between Two Vertices Using DFS

Question

Find one path from A to F using DFS.

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

Solution

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

function findPath(graph, start, target, visited = new Set()) {
  if (start === target) {
    return [start];
  }

  visited.add(start);

  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      const path = findPath(graph, neighbor, target, visited);

      if (path.length > 0) {
        return [start, ...path];
      }
    }
  }

  return [];
}

console.log(findPath(graph, "A", "F"));

Output

[ 'A', 'B', 'D', 'F' ]

Answer

DFS finds this path:

A → B → D → F

DFS finds a valid path, but it does not necessarily find the shortest path.

Question 5: Count All Vertices Using DFS

Question

Count how many vertices are reachable from A.

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

Solution

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

function countVertices(graph, start, visited = new Set()) {
  if (visited.has(start)) {
    return 0;
  }

  visited.add(start);

  let count = 1;

  for (const neighbor of graph[start]) {
    count += countVertices(graph, neighbor, visited);
  }

  return count;
}

console.log(countVertices(graph, "A"));

Output

5

Answer

The five reachable vertices are:

A, B, C, D, E

Therefore, DFS visits 5 vertices.

Question 6: Detect a Cycle in an Undirected Graph Using DFS

Question

Determine whether the following undirected graph contains a cycle:

const graph = {
  A: ["B", "C"],
  B: ["A", "C"],
  C: ["A", "B"]
};

Solution

In an undirected graph, we keep track of the parent vertex. If DFS reaches an already visited vertex that is not the parent, a cycle exists.

const graph = {
  A: ["B", "C"],
  B: ["A", "C"],
  C: ["A", "B"]
};

function hasCycle(graph, vertex, visited, parent) {
  visited.add(vertex);

  for (const neighbor of graph[vertex]) {
    if (!visited.has(neighbor)) {
      if (hasCycle(graph, neighbor, visited, vertex)) {
        return true;
      }
    } else if (neighbor !== parent) {
      return true;
    }
  }

  return false;
}

function detectCycle(graph) {
  const visited = new Set();

  for (const vertex in graph) {
    if (!visited.has(vertex)) {
      if (hasCycle(graph, vertex, visited, null)) {
        return true;
      }
    }
  }

  return false;
}

console.log(detectCycle(graph));

Output

true

Answer

The graph contains a cycle:

A → B → C → A

Therefore, the result is true.

Question 7: Count Connected Components Using DFS

Question

The graph contains multiple disconnected groups:

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

Use DFS to count the number of connected components.

Solution

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

function dfs(graph, vertex, visited) {
  visited.add(vertex);

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

function countComponents(graph) {
  const visited = new Set();
  let count = 0;

  for (const vertex in graph) {
    if (!visited.has(vertex)) {
      count++;

      dfs(graph, vertex, visited);
    }
  }

  return count;
}

console.log(countComponents(graph));

Output

3

Answer

There are three connected components:

A — B

C — D

E

Therefore, the answer is 3.

Question 8: Find the Maximum Depth of a Graph Path

Question

Find the maximum depth reachable from vertex A.

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

Solution

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

function maxDepth(graph, vertex, visited = new Set()) {
  visited.add(vertex);

  let depth = 0;

  for (const neighbor of graph[vertex]) {
    if (!visited.has(neighbor)) {
      depth = Math.max(
        depth,
        maxDepth(graph, neighbor, visited)
      );
    }
  }

  return depth + 1;
}

console.log(maxDepth(graph, "A"));

Output

3

Answer

The deepest path is:

A → C → E → F

The path contains 4 vertices, which corresponds to a recursive depth value of 3 edges from A.

Question 9: Count Islands in a Grid Using DFS

Question

In the following grid, 1 represents land and 0 represents water.

Count the number of separate islands.

const grid = [
  [1, 1, 0, 0],
  [1, 0, 0, 1],
  [0, 0, 1, 1],
  [0, 0, 0, 0]
];

Cells are connected horizontally or vertically.

Solution

const grid = [
  [1, 1, 0, 0],
  [1, 0, 0, 1],
  [0, 0, 1, 1],
  [0, 0, 0, 0]
];

function dfs(grid, row, col) {
  const rows = grid.length;
  const cols = grid[0].length;

  if (
    row < 0 ||
    row >= rows ||
    col < 0 ||
    col >= cols ||
    grid[row][col] === 0
  ) {
    return;
  }

  grid[row][col] = 0;

  dfs(grid, row - 1, col);
  dfs(grid, row + 1, col);
  dfs(grid, row, col - 1);
  dfs(grid, row, col + 1);
}

function countIslands(grid) {
  let count = 0;

  for (let row = 0; row < grid.length; row++) {
    for (let col = 0; col < grid[0].length; col++) {
      if (grid[row][col] === 1) {
        count++;

        dfs(grid, row, col);
      }
    }
  }

  return count;
}

console.log(countIslands(grid));

Output

2

Answer

There are 2 separate islands.

DFS explores all connected land cells belonging to an island before moving to another island.

Question 10: Perform DFS on a Grid to Find Whether a Target Exists

Question

Given the following grid, start from (0, 0) and determine whether the target value 9 can be reached.

const grid = [
  [1, 1, 0],
  [0, 1, 0],
  [0, 1, 9]
];

You can move up, down, left, or right.

Solution

const grid = [
  [1, 1, 0],
  [0, 1, 0],
  [0, 1, 9]
];

function dfs(grid, row, col, visited) {
  const rows = grid.length;
  const cols = grid[0].length;

  if (
    row < 0 ||
    row >= rows ||
    col < 0 ||
    col >= cols
  ) {
    return false;
  }

  if (grid[row][col] === 0) {
    return false;
  }

  if (visited.has(`${row},${col}`)) {
    return false;
  }

  if (grid[row][col] === 9) {
    return true;
  }

  visited.add(`${row},${col}`);

  return (
    dfs(grid, row - 1, col, visited) ||
    dfs(grid, row + 1, col, visited) ||
    dfs(grid, row, col - 1, visited) ||
    dfs(grid, row, col + 1, visited)
  );
}

console.log(dfs(grid, 0, 0, new Set()));

Output

true

Answer

The target 9 can be reached.

One valid path is:

(0,0)
 ↓
(0,1)
 ↓
(1,1)
 ↓
(2,1)
 ↓
(2,2)

Therefore, DFS returns true.

Key Takeaways

  • DFS stands for Depth-First Search.
  • DFS explores one path deeply before backtracking.
  • DFS can be implemented using recursion or a stack.
  • A visited set prevents repeated processing.
  • DFS can determine whether a path exists.
  • DFS can find a valid path between two vertices.
  • DFS can detect cycles in graphs.
  • DFS can count connected components.
  • DFS can be used to solve grid problems such as counting islands.
  • Unlike BFS, DFS does not guarantee the shortest path in an unweighted graph.

FAQs

1. What is DFS in data structures?

DFS, or Depth-First Search, is a graph traversal algorithm that explores a path as deeply as possible before backtracking.

2. Which data structures can be used to implement DFS?

DFS can be implemented using a Stack or through recursion, where the function call stack acts like a stack.

3. Why is a visited set needed in DFS?

A visited set prevents DFS from visiting the same vertex repeatedly, especially when the graph contains cycles.

4. Can DFS find the shortest path?

DFS can find a path, but it does not generally guarantee the shortest path in an unweighted graph. BFS is normally preferred for shortest-path problems in unweighted graphs.

5. Can DFS detect cycles?

Yes. DFS can be used to detect cycles in both directed and undirected graphs, with different detection techniques for each.

6. Can DFS be used on a matrix or grid?

Yes. A grid can be treated as a graph, and DFS can be used for problems such as island counting, maze exploration, and connected-region detection.

7. What is the main difference between BFS and DFS?

BFS explores level by level using a queue, while DFS explores deeply using recursion or a stack before backtracking.

Written by Shubhranshu Shekhar, who has trained 20000+ students in coding.

Related Posts

Scroll to Top