Graph traversals·12 min

Breadth-first search

0 / 1

# grade this stage (from your course directory)
npx theinference test --stage bfs --watch

Implement BFS that returns every reachable node and its hop-distance from a start node, stopping past maxHops. Classic queue-based BFS: a dist map, expand the frontier ring by ring, mark each node visited on enqueue.

Your task

Implement runBfsDistances

This is an adapter step. Implement bfs(store, startId, maxHops, type, dir) returning rows {node, dist} sorted by (dist, node); the adapter flattens them to [node, dist] pairs. The fixture runs BFS from Kevin Bacon (id 0), ACTED_IN, BOTH, maxHops=2 — his movies at distance 1, his co-stars at distance 2 (19 rows total).

src/traversal.ts

export function bfs(store, startId, maxHops, type, dir) {
  const dist = new Map([[startId, 0]]);
  let frontier = [startId], d = 0;
  while (frontier.length && d < maxHops) {
    const next = [];
    for (const cur of frontier)
      for (const nb of store.neighbors(cur, type, dir))
        if (!dist.has(nb)) { dist.set(nb, d + 1); next.push(nb); }  // visited on ENQUEUE
    frontier = next; d++;
  }
  return [...dist].map(([node, dd]) => ({ node, dist: dd }))
    .sort((a, b) => a.dist - b.dist || a.node - b.node);
}

Mark visited on enqueue, not dequeue

Mark a node visited when you first reach it (enqueue), not when you process it (dequeue). Otherwise the same node enters the frontier multiple times — its distance and your runtime both blow up. This is the #1 BFS bug.

How it's graded

Adapter mode: the harness calls runBfsDistances(0, 2, 'ACTED_IN', 'BOTH') and compares your [node, dist] rows to the fixture (shape [19, 2]), sorted by (dist, node). Distance 0 is the start itself.

BFS, DFS, and the frontier DFS & cycle detection