Graph Traversal: BFS and DFS

Graph Traversal: BFS and DFS — DSA Tutorial - HTML5ANDCSS3

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
}

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
}

Why visited is not optional

Breadth first - a queue

Depth first - a stack, or recursion

Choosing

Weighted graphs