Skip to main content

< Back to Data Structures and Algorithms

Graph Algorithms · Graphs

Depth-First and Breadth-First Print

Prints every node reachable from a source, three ways: depth first with a stack, depth first by recursion, and breadth first with a queue.

Step through it

Examples
Edge cases
graph
abcdef

source = "a"

Step 0 of 17

Output

Running… play or step to the end.

The code

/* Depth First Search (DFS)
   - Implements a Stack data structure (Last in, First Out).
   -- => 'c'  Always take from the top '.pop()'
         'b'  Always add to the top '.push()'
         'a'
         ===
   - Can be implemented either iteratively or recursively. */

// DFS Iterative approach
const depthFirstIterativePrint = (graph, source) => {
  // Initialise the stack with the source node.
  const stack = [ source ]

  // Iterate while stack is still populated.
  while (stack.length) {
    // .pop() the top item off the stack.
    const current = stack.pop()
    console.log(current)

    // Iterate over each node adjacent to the current node.
    for (let neighbour of graph[current]) {
      // .push() the adjacent node to the top of the stack.
      stack.push(neighbour)
    }
  }
}

// DFS Recursive approach
const depthFirstRecursivePrint = (graph, currentNode) => {
  /* No explicit base case,.
     the implicit base case is when the recursed node has no neighbours. */

  // currentNode is the top node on the call stack.
  console.log(currentNode)

  // Iterate over each node adjacent to the current node.
  for (let neighbour of graph[currentNode]) {
    // Recursively call this method for each adjacent node.
    depthFirstRecursivePrint(graph, neighbour)
  }
}



/* Breadth First Search (BFS)
   - Implements a Queue data structure (First In, First Out).
   -- => ['a', 'b', 'c']

   --- Add to the right: ['a', 'b', 'c'] <= 'd'
   -- => ['a', 'b', 'c', 'd']

   --- Take from the left: 'a' <= ['b', 'c', 'd']
   -- => ['b', 'c', 'd']

   - Can only be implemented iteratively. */

// BFS approach
const breadthFirstPrint = (graph, source) => {
  const queue = [ source ]

  // Iterate while the queue is still populated.
  while (queue.length) {
    // .shift() the front node out of the queue.
    const current = queue.shift()
    console.log(current)

    // Iterate over each node adjacent to the current node.
    for (let neighbour of graph[current]) {
      // .push() the adjacent node to the end of the queue.
      queue.push(neighbour)
    }
  }
}

// A directed acyclic graph, represented as an adjacency list.
const graph = {
  a: ['b', 'c'],
  b: ['d'],
  c: ['e'],
  d: ['f'],
  e: [],
  f: []
}

depthFirstIterativePrint(graph, 'a')
depthFirstRecursivePrint(graph, 'a')

breadthFirstPrint(graph, 'a')

View it on GitHub (opens in a new tab)