Graph BFS

Traverse a graph breadth-first from a start node using a FIFO queue, visiting nearer nodes first.

Time O(V + E) Space O(V) Graph bfs

How it works

Traverse a graph breadth-first from a start node using a FIFO queue, visiting nearer nodes first.

Implementation

function graphBfsOp(state, start) {
  const adjHead = state.adjHead;
  const adjTo = state.adjTo;
  const adjNext = state.adjNext;
  const nodeCount = state.nodeCount;
  const visited = [];
  let v = 0;
  while (v < nodeCount) {
    visited[v] = 0;
    v = v + 1;
  }
  const queue = [];
  let head = 0;
  queue[0] = start;
  visited[start] = 1;
  visitNode(start);
  while (head < queue.length) {
    const node = queue[head];
    head = head + 1;
    traverseNode(node);
    let e = adjHead[node];
    while (e !== -1) {
      const nb = adjTo[e];
      compareKeys(node, nb);
      if (visited[nb] === 0) {
        visited[nb] = 1;
        queue[queue.length] = nb;
        linkNodes(node, nb);
        visitNode(nb);
      }
      e = adjNext[e];
    }
  }
  finish();
}