Graph Traversal Using Generator Functions

Here are some functions that perform graph traversals using generator functions.

The generator functions allow the caller to pause the traversal at any node, call a subroutine, then stop or resume the traversal.

breadth-first search:

export function* bfsNodes(nodeRoot) {
  let queue = []
  queue.push(nodeRoot)

  while (queue.length > 0) {
    const node = queue.shift()
    yield node
    queue = queue.concat(node.children)
  }
}

depth-first search:

export function* dfsNodes(node) {
  const visit = function*(node, depth) {
    yield { node, depth }
    const children = node.children
    for (let i = 0; i < children.length; i++) {
      yield* visit(children[i], depth + 1)
    }
  }
  yield* visit(node, 0)
}