Implementing Graph Traversal in JavaScript

Graph traversal is one of the most fundamental skills in computer science, and implementing it from scratch in JavaScript gives you deep insight into how algorithms like shortest-path finders, social network analyzers, and web crawlers actually work under the hood. In this topic, you will build a Graph class step by step, add the ability to connect vertices with edges, and then implement both Breadth-First Search (BFS) and Depth-First Search (DFS) — the two cornerstone traversal strategies — in multiple styles. By the end, you will understand not just how to write these algorithms, but why each design decision is made and when to reach for one approach over another.

A graph is a collection of vertices (also called nodes) connected by edges. Unlike trees, graphs can have cycles, disconnected components, and edges that point in both directions. The most practical way to represent a graph in JavaScript is through an adjacency list — a data structure where each vertex maps to an array (or set) of its neighbors. Adjacency lists are memory-efficient for sparse graphs (graphs where most pairs of vertices are not connected), which describes the vast majority of real-world graphs.

Setting Up the Graph Class in JavaScript

The first step is defining a Graph class with a constructor that establishes an empty adjacency list. You can use a plain JavaScript object or a Map; a plain object is idiomatic and slightly simpler for string-keyed vertices, while a Map supports non-string keys and has cleaner semantics. The examples below use a plain object, but the concepts transfer directly to Map.

class Graph {
  constructor() {
    // The adjacency list stores each vertex as a key
    // and an array of its neighbors as the value.
    this.adjacencyList = {};
  }
}

Next, add an addVertex method. This method accepts a vertex name and creates a new entry in the adjacency list with an empty array. A critical detail is the duplicate guard: if you add the same vertex twice without checking, you will silently overwrite its existing neighbor array and lose all recorded edges. Always check whether the vertex already exists first.

addVertex(vertex) {
  // Guard: only add the vertex if it does not already exist.
  if (!this.adjacencyList[vertex]) {
    this.adjacencyList[vertex] = [];
  }
}

With this guard in place, calling addVertex("A") twice is safe — the second call is simply a no-op. Here is a concrete setup for a small graph representing cities connected by roads:

const graph = new Graph();
graph.addVertex("Tokyo");
graph.addVertex("Seoul");
graph.addVertex("Beijing");
graph.addVertex("Shanghai");

// adjacencyList is now:
// { Tokyo: [], Seoul: [], Beijing: [], Shanghai: [] }

Adding Edges to the Graph

An addEdge(v1, v2) method connects two vertices. For an undirected graph (where a connection goes both ways, like a two-lane road), you push each vertex into the other's neighbor array. For a directed graph (a one-way street), you only push v2 into v1's list.

addEdge(v1, v2) {
  // Validate that both vertices exist before modifying the list.
  if (!this.adjacencyList[v1] || !this.adjacencyList[v2]) {
    console.error("One or both vertices do not exist.");
    return;
  }
  // For an undirected graph, add both directions.
  this.adjacencyList[v1].push(v2);
  this.adjacencyList[v2].push(v1);
}

Validation is essential. Without it, a typo like addEdge("Tokyo", "Tokyoo") would silently create a dangling edge pointing to undefined, corrupting traversal results.

graph.addEdge("Tokyo", "Seoul");
graph.addEdge("Tokyo", "Beijing");
graph.addEdge("Seoul", "Shanghai");
graph.addEdge("Beijing", "Shanghai");

// adjacencyList is now:
// {
//   Tokyo:    ["Seoul", "Beijing"],
//   Seoul:    ["Tokyo", "Shanghai"],
//   Beijing:  ["Tokyo", "Shanghai"],
//   Shanghai: ["Seoul", "Beijing"]
// }

Removing an edge is equally important for maintaining list integrity. A removeEdge method filters out the target vertex from each side of the connection using Array.prototype.filter, which returns a new array containing only the elements that pass the test — leaving out the vertex you want to remove.

removeEdge(v1, v2) {
  if (!this.adjacencyList[v1] || !this.adjacencyList[v2]) return;
  // Replace each neighbor array with a filtered version.
  this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2);
  this.adjacencyList[v2] = this.adjacencyList[v2].filter(v => v !== v1);
}

After graph.removeEdge("Tokyo", "Seoul"), Tokyo's list becomes ["Beijing"] and Seoul's list becomes ["Shanghai"]. The connection is cleanly severed on both sides.

Implementing Breadth-First Search (BFS)

BFS explores a graph level by level, visiting all vertices one edge away from the start before visiting vertices two edges away, and so on. This layered expansion makes BFS the natural choice for finding the shortest path between two vertices in an unweighted graph — the first time BFS reaches a target vertex, it has done so via the fewest possible edges.

The core data structure for BFS is a queue (first-in, first-out). JavaScript arrays can simulate a queue using push to enqueue and shift to dequeue (though for performance-critical code a dedicated queue class is preferable because shift is O(n)). A visited set prevents revisiting vertices in cyclic graphs.

bfs(start) {
  // 1. Validate the starting vertex.
  if (!this.adjacencyList[start]) return [];

  const queue   = [start];   // Initialize queue with the start vertex.
  const visited = new Set([start]); // Mark start as visited immediately.
  const results = [];

  while (queue.length > 0) {
    // 2. Dequeue the front vertex.
    const vertex = queue.shift();
    results.push(vertex); // Record it in the traversal order.

    // 3. Examine each neighbor of this vertex.
    for (const neighbor of this.adjacencyList[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);   // Mark as visited before enqueuing
        queue.push(neighbor);    // to avoid duplicates in the queue.
      }
    }
  }

  return results; // BFS traversal order
}

A subtle but important detail: mark a neighbor as visited when you enqueue it, not when you dequeue it. Marking on dequeue allows the same vertex to be enqueued multiple times by different neighbors, wasting work and potentially corrupting the traversal order in certain graph shapes.

Running BFS on the city graph from the start vertex "Tokyo":

graph.bfs("Tokyo");
// Returns: ["Tokyo", "Seoul", "Beijing", "Shanghai"]
// Level 0: Tokyo
// Level 1: Seoul, Beijing  (both one edge from Tokyo)
// Level 2: Shanghai        (two edges from Tokyo)

Implementing Depth-First Search — Recursive Approach

DFS explores as far as possible along one branch before backtracking. The recursive approach expresses this beautifully because the call stack itself acts as the mechanism for backtracking — when a function call returns, execution automatically resumes at the previous vertex.

dfsRecursive(start) {
  if (!this.adjacencyList[start]) return [];

  const visited = new Set();
  const results = [];
  const adjacencyList = this.adjacencyList; // Capture for use in helper

  function dfsHelper(vertex) {
    // Mark this vertex visited and record it.
    visited.add(vertex);
    results.push(vertex);

    // Recurse on each unvisited neighbor.
    for (const neighbor of adjacencyList[vertex]) {
      if (!visited.has(neighbor)) {
        dfsHelper(neighbor); // Go as deep as possible before backtracking.
      }
    }
    // Base case is implicit: if all neighbors are visited, the loop
    // does nothing and this call simply returns to its caller.
  }

  dfsHelper(start);
  return results;
}

The base case does not need an explicit if check because the for loop simply does nothing when every neighbor has already been visited, and the function returns naturally. This is an example of a self-limiting recursion driven by the data rather than a hard-coded stopping condition.

graph.dfsRecursive("Tokyo");
// Possible output: ["Tokyo", "Seoul", "Shanghai", "Beijing"]
// The traversal dives from Tokyo → Seoul → Shanghai → Beijing
// before backtracking, visiting siblings only after exhausting a branch.

Implementing Depth-First Search — Iterative Approach

The iterative DFS replaces the implicit call stack with an explicit stack data structure (last-in, first-out). JavaScript arrays function well as stacks via push and pop. This version is important because deep recursive DFS on large graphs can exceed JavaScript's call stack limit (typically around 10,000–15,000 frames depending on the environment), causing a RangeError: Maximum call stack size exceeded. The iterative approach has no such limitation.

dfsIterative(start) {
  if (!this.adjacencyList[start]) return [];

  const stack   = [start]; // Initialize stack with start vertex.
  const visited = new Set();
  const results = [];

  while (stack.length > 0) {
    // Pop from the top of the stack.
    const vertex = stack.pop();

    // Only process this vertex if it has not been visited yet.
    // (It may have been pushed multiple times by different neighbors.)
    if (!visited.has(vertex)) {
      visited.add(vertex);
      results.push(vertex);

      // Push all unvisited neighbors onto the stack.
      // They will be processed in reverse order compared to the
      // recursive version because of LIFO behavior.
      for (const neighbor of this.adjacencyList[vertex]) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }

  return results;
}

Notice that in the iterative version, the visited check occurs on pop, not on push. This is because a vertex can be pushed onto the stack multiple times by different neighbors before it is ever processed. Checking on pop ensures correctness even when duplicates exist in the stack. This contrasts with BFS, where marking on enqueue is cleaner and more efficient.

graph.dfsIterative("Tokyo");
// Possible output: ["Tokyo", "Beijing", "Shanghai", "Seoul"]
// Note: The specific order may differ from recursive DFS because
// LIFO processing reverses the neighbor visitation order.

Comparing BFS and DFS Outputs in Practice

Running both algorithms on the same graph illuminates their different priorities. Consider a slightly larger graph to make the contrast vivid:

const g = new Graph();
["A","B","C","D","E","F"].forEach(v => g.addVertex(v));
g.addEdge("A","B"); g.addEdge("A","C");
g.addEdge("B","D"); g.addEdge("C","E");
g.addEdge("D","F");

//  Graph structure:
//       A
//      / \
//     B   C
//     |   |
//     D   E
//     |
//     F

console.log(g.bfs("A"));
// ["A", "B", "C", "D", "E", "F"]
// Visits all vertices at distance 1 (B, C) before distance 2 (D, E),
// then distance 3 (F). Ideal for asking: "What is the shortest path from A to E?"

console.log(g.dfsRecursive("A"));
// ["A", "B", "D", "F", "C", "E"]
// Dives A → B → D → F before backtracking to explore C → E.
// Ideal for asking: "Does a path exist from A to F?" or "Is this graph cyclic?"

The table below summarizes the key characteristics and use cases for each algorithm:

A practical rule of thumb: reach for BFS when proximity or the minimum number of steps matters (GPS routing on an unweighted road network, degrees of separation in a social graph). Reach for DFS when you need to exhaustively explore paths, detect cycles, or determine reachability (dependency resolution, topological ordering of tasks, puzzle solving). Testing both traversals on the same Graph instance and comparing their outputs side by side is one of the most effective ways to build an intuitive, lasting understanding of these algorithms.