modulito.svg
modulitos

homeblogprojectscontact

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)
}
create commons icon
modulitos, 2019