Breadth-first graph traversal (BFS)

breadth-first traversal.js

function breadthFirstTraverse(connections, start = 0) {
  let stack = [[start, 0]]; // keep node index & current depth
  let visited = new Set;

  while (stack.length) {
    let newStack = [];
    log('Current stack:', stack);

    for (let [i, depth] of stack) {
      log(`Visit ${i} (depth: ${depth})`);
      visited.add(i);

      for (let k = 0; k < connections[i].length; k++) {
        if (k === i)
          continue;

        if (connections[i][k] === 0)
          continue;

        if (visited.has(k)) {
          log(`Not going from ${i} to ${k} (already visited):`, visited);
        } else {
          log(`Going from ${i} to ${k}.`);
          newStack.push([k, depth + 1]);
        }
      }

      log(`Finished with ${i}`);
    }

    stack = newStack;
  }
}

function log(...args) {
  if (log.enabled) {
    console.log(...args);
  }
}

log.enabled = true;