Meeting Graph Algorithms with NodeJS and Javascript

A graph from ep. 7 is inert without traversal. This episode implements BFS and DFS — foundation for shortest paths (unweighted), cycles, and topological order.

What you'll learn:

• BFS with a queue and visited set
• DFS recursive and iterative
• when BFS finds shortest path (no edge weights)
• cycle detection with DFS

Prerequisites: graphs (ep. 7).

BFS and DFS: traverse without infinite loops

Back in Part 7 we built a Graph structure with nodes and edges. Having the data structure is great, but without algorithms to navigate it, we're just storing a map without being able to use it. That's what this post is about: Breadth-First Search (BFS) and Depth-First Search (DFS)—the two fundamental algorithms for exploring a graph.

To keep things concrete, we'll use this graph for all our examples:

graph LR
  A --- B
  A --- C
  B --- D
  B --- E
  C --- F
  C --- G

Starting from node A, BFS and DFS will each visit all nodes—but in a completely different order.

Hands-on

First The Theory

BFS — Breadth-First Search

BFS uses a queue. It visits all neighbours of the current node before moving deeper. Think of it as expanding a wave: first every node one hop away, then every node two hops away, and so on.

graph LR
  A["A (1st)"] --- B["B (2nd)"]
  A --- C["C (3rd)"]
  B --- D["D (4th)"]
  B --- E["E (5th)"]
  C --- F["F (6th)"]
  C --- G["G (7th)"]

BFS visit order from A: A → B → C → D → E → F → G

DFS — Depth-First Search

DFS uses a stack (or recursion). It dives as deep as possible along one path before backtracking. Think of it as exploring a maze: go all the way down one corridor, then come back and try the next one.

graph LR
  A["A (1st)"] --- B["B (2nd)"]
  A --- C["C (5th)"]
  B --- D["D (3rd)"]
  B --- E["E (4th)"]
  C --- F["F (6th)"]
  C --- G["G (7th)"]

DFS visit order from A (following insertion order): A → B → D → E → C → F → G

Now The Practice

We'll reuse the Graph from Part 7. Paste the full file to start:

class Graph {
  constructor() {
    this.numberOfNodes = 0
    this.adjacentList = {}
  }
 
  add(node) {
    this.adjacentList[node] = []
    this.numberOfNodes++
  }
 
  addEdge(node1, node2) {
    this.adjacentList[node1].push(node2)
    this.adjacentList[node2].push(node1)
  }
}

Now let's add the BFS method to the Graph class:

  bfs(start) {
    const visited = new Set()
    const queue = [start]
    const order = []
 
    visited.add(start)
 
    while (queue.length) {
      const node = queue.shift()
      order.push(node)
 
      for (const neighbour of this.adjacentList[node]) {
        if (!visited.has(neighbour)) {
          visited.add(neighbour)
          queue.push(neighbour)
        }
      }
    }
 
    return order
  }

Breaking it down:

• We start with a Set to track visited nodes (so we don't loop forever in cyclic graphs) and a queue seeded with the start node.
• On each iteration we pull the front of the queue (shift()), record it, and enqueue all its unvisited neighbours.
• Because we process the queue front-to-back, we naturally visit nodes level by level.

Now let's add DFS:

  dfs(start) {
    const visited = new Set()
    const order = []
 
    const explore = (node) => {
      visited.add(node)
      order.push(node)
      for (const neighbour of this.adjacentList[node]) {
        if (!visited.has(neighbour)) {
          explore(neighbour)
        }
      }
    }
 
    explore(start)
    return order
  }

Breaking it down:

• We use a recursive helper explore that marks a node visited, records it, then immediately recurses into each unvisited neighbour.
• Because we go deep into the first neighbour before considering siblings, we get the depth-first order.

Let's test both. After the class, add:

const g = new Graph()
g.add('A')
g.add('B')
g.add('C')
g.add('D')
g.add('E')
g.add('F')
g.add('G')
 
g.addEdge('A', 'B')
g.addEdge('A', 'C')
g.addEdge('B', 'D')
g.addEdge('B', 'E')
g.addEdge('C', 'F')
g.addEdge('C', 'G')
 
console.log('BFS from A:', g.bfs('A'))
console.log('DFS from A:', g.dfs('A'))

Run it:

node graph-algorithms.js

Expected output:

BFS from A: [ 'A', 'B', 'C', 'D', 'E', 'F', 'G' ]
DFS from A: [ 'A', 'B', 'D', 'E', 'C', 'F', 'G' ]

AWESOME!

Both algorithms visited all 7 nodes, but in completely different orders. BFS went wide (all direct neighbours of A first), while DFS went deep (followed the B branch all the way down before touching C).

Can I do iterative DFS instead of recursive?

Absolutely! Replace the explore function with a stack:

  dfsIterative(start) {
    const visited = new Set()
    const stack = [start]
    const order = []
 
    while (stack.length) {
      const node = stack.pop()
      if (visited.has(node)) continue
      visited.add(node)
      order.push(node)
      for (const neighbour of this.adjacentList[node]) {
        if (!visited.has(neighbour)) stack.push(neighbour)
      }
    }
 
    return order
  }

The iterative version uses an explicit stack instead of the call stack—safer for very large or deep graphs where recursion could hit the stack limit.

Edge cases: visited set, shift, stack depth

Without a visited Set, any cycle loops forever. Mark nodes when you enqueue/push, not only when you process.

Deep recursive DFS can exceed Node's stack — use an explicit stack for large graphs.

BFS on weighted graphs does not guarantee cheapest path — use Dijkstra with a priority queue.

TL;DR — BFS vs DFS

Next steps

• Sorting (ep. 15)
• Binary search (ep. 16)

Before you go

BFS or DFS in production? Comment if the sample graph has a bug.