Skip to main content
HTML5ANDCSS3 logoHTML5ANDCSS3Tools and Tutorials

Graphs

Graph Traversal: BFS and DFS

Written by Updated

BFS and DFS differ by one thing: a queue or a stack. Everything else is identical, including the visited set you cannot leave out.

Why visited is not optional

A tree has no cycles, so you can walk it without tracking where you have been. A graph can loop back, and without a visited set the traversal runs forever.

Breadth first - a queue

Visit all neighbours, then their neighbours. Reaches nodes in order of distance, which is why it finds shortest paths in unweighted graphs.

BFS, with distances

javascript

function bfs(graph, start) {
  const visited = new Set([start])
  const queue = [start]
  let head = 0
  const order = []

  while (head < queue.length) {
    const node = queue[head++]     // pointer, not shift()
    order.push(node)

    for (const next of graph.get(node) || []) {
      if (!visited.has(next)) {
        visited.add(next)          // mark on enqueue, not on dequeue
        queue.push(next)
      }
    }
  }

  return order
}

// Shortest path length in an unweighted graph.
function shortestPath(graph, start, target) {
  if (start === target) return 0

  const visited = new Set([start])
  const queue = [[start, 0]]
  let head = 0

  while (head < queue.length) {
    const [node, distance] = queue[head++]

    for (const next of graph.get(node) || []) {
      if (next === target) return distance + 1
      if (!visited.has(next)) {
        visited.add(next)
        queue.push([next, distance + 1])
      }
    }
  }

  return -1
}

const demoGraph = new Map([["a", ["b", "c"]], ["b", ["d"]], ["c", []], ["d", []]])
console.log(bfs(demoGraph, "a"))  // visit order from a

Marking visited when you enqueue rather than when you dequeue is the detail that matters. Mark on dequeue and the same node gets queued many times before it is processed once.

Depth first - a stack, or recursion

Follow one path as far as it goes, then back up and try the next.

DFS, both ways

javascript

// Recursive — reads better, limited by stack depth.
function dfs(graph, node, visited = new Set(), order = []) {
  visited.add(node)
  order.push(node)

  for (const next of graph.get(node) || []) {
    if (!visited.has(next)) dfs(graph, next, visited, order)
  }

  return order
}

// Iterative — no depth limit.
function dfsIterative(graph, 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 next of graph.get(node) || []) {
      if (!visited.has(next)) stack.push(next)
    }
  }

  return order
}

const demoGraph = new Map([["a", ["b", "c"]], ["b", []], ["c", []]])
console.log(dfs(demoGraph, "a"))
console.log(dfsIterative(demoGraph, "a"))

In the iterative version the visited check happens on pop, because a node can be pushed more than once before it is processed.

Choosing

  • Shortest path, unweighted - BFS. DFS finds a path, not the shortest.
  • Nearest anything - BFS, for the same reason.
  • Does a path exist / connected components - either. DFS is usually shorter to write.
  • Cycle detection, topological sort - DFS.
  • Very deep graph - BFS, or iterative DFS. Recursive DFS will overflow.

Both are O(nodes + edges) in time. BFS holds a whole level in memory; DFS holds one path. On a wide, shallow graph DFS uses less memory, and on a deep, narrow one BFS does.

Weighted graphs

BFS finds the fewest edges, not the lowest cost. The moment edges have weights you need Dijkstra's algorithm, which is BFS with a priority queue instead of a plain one.

PreviousGraphs and How to Represent ThemNextTopological Sort