Graph Traversal with Breadth-First and Depth-First Search in JavaScript

Many front-end engineering problems—from walking the DOM tree and resolving module dependency graphs to finding the shortest path between UI states—are fundamentally graph traversal problems. When data is structured as nodes connected by edges rather than a flat array, we rely on two foundational traversal strategies: Breadth-First Search (BFS) and Depth-First Search (DFS).

Both algorithms visit every reachable vertex V and edge E in linear O(V + E) time complexity, but the order in which they explore nodes differs based on their underlying data structure:

• Breadth-First Search (BFS) uses a First-In, First-Out (FIFO queue) to explore all neighbors at the current depth level before moving to the next level, making it ideal for finding the shortest path in an unweighted graph.
• Depth-First Search (DFS) uses a Last-In, First-Out (LIFO stack or the call stack via recursion) to plunge as deep as possible along each branch before backtracking.

Example #

Input : An adjacency list representing a directed graph and a starting node 'A'
Output : Ordered array of visited nodes in O(V + E) time complexity.

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

breadthFirstSearch(graph, 'A');
// output: ['A', 'B', 'C', 'D', 'E', 'F'] (level by level)

depthFirstSearch(graph, 'A');
// output: ['A', 'B', 'D', 'E', 'F', 'C'] (branch by branch)

Implementation #

To prevent infinite loops when traversing cyclic graphs, both implementations maintain a Set of already-visited nodes. In breadthFirstSearch, we track a queueIndex pointer rather than calling queue.shift() inside the loop so dequeue operations stay O(1) instead of shifting remaining array elements in O(n).

/**
 * Breadth-First Search (BFS) — explores level by level using a FIFO queue.
 * Time Complexity: O(V + E) | Space Complexity: O(V)
 */
function breadthFirstSearch(graph, startNode) {
  const visited = new Set([startNode]);
  const queue = [startNode];
  const result = [];
  let queueIndex = 0;

  while (queueIndex < queue.length) {
    const currentNode = queue[queueIndex];
    queueIndex++;
    result.push(currentNode);

    const neighbors = graph[currentNode] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return result;
}

/**
 * Depth-First Search (DFS) — explores deep along each branch before backtracking.
 * Time Complexity: O(V + E) | Space Complexity: O(V)
 */
function depthFirstSearch(graph, startNode, visited = new Set(), result = []) {
  visited.add(startNode);
  result.push(startNode);

  const neighbors = graph[startNode] || [];
  for (const neighbor of neighbors) {
    if (!visited.has(neighbor)) {
      depthFirstSearch(graph, neighbor, visited, result);
    }
  }

  return result;
}

/**
 * Practical DOM example: Iterative DFS over a DOM subtree without recursion stack limits
 */
function collectFocusableNodes(rootElement) {
  const stack = [rootElement];
  const matches = [];

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

    if (
      node.matches &&
      node.matches('a[href], button:not([disabled]), input:not([disabled])')
    ) {
      matches.push(node);
    }

    // Push children in reverse order so left-to-right DOM order is preserved when popped
    const children = node.children || [];
    for (let i = children.length - 1; i >= 0; i--) {
      stack.push(children[i]);
    }
  }

  return matches;
}

Main Point: Both BFS and DFS visit every reachable vertex and edge in O(V + E) time—choose BFS with a FIFO queue when you need level-order traversal or the shortest path in an unweighted graph, and choose DFS with recursion or a LIFO stack when exploring full branches, trees, or dependency hierarchies.

Credits #

Photo by Lydia Verbeke

← Home