Master the Coding Interview: Depth First Search using Stacks and a Graph in JavaScript

Marika Lam

·

Follow

2 min read

·

Jun 25, 2024

--

Share

What is Depth First Search?

• Depth First Search is an algorithm for travesing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each brand before backtracking.
• Depth First Search simply says that once you have visited a vertex, start exploring its child nodes and sub child nodes until there is no node to explore for that vertex and then move to next vertex.
• It’s also called pre-order traversal.

- start from the root element(it can be any)
- push the root in stack.
- Explore its child. (check if visited or not)
- if not visited, push to stack, and repeat the process until we explore all the 
vertices.
- if all nodes are processed, get value from stack and check for vertices that are not visited.

Explanation

• Below is the graph object where we pass that into the parameter of the dfs() method.
• DFS algorithm is implemented using a stack data feature, which holds the nodes that are to be processed in the order they were discovered.

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

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

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

    if (!visited.has(vertex)) {
      visited.add(vertex);
      result.push(vertex);

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

  return result;
}

dfs(graph, 'A'); // ['A', 'D', 'E', 'F', 'B', 'C']