Graphs

Graph BFS

Walk a graph in breadth-first order from a starting node. Every node is visited at its shortest-path distance from the start.

Algorithm

Canonical input graph (edges 1-2, 1-3, 2-4, 3-4, 4-5, 5-6 starting at node 1) finishes after six node visits; the printed BFS order is [1, 2, 3, 4, 5, 6].

Basic Implementation

basic.sql 
.mode list
.headers off
CREATE TABLE edge(u INTEGER, v INTEGER);
INSERT INTO edge(u, v) VALUES
  (1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (5, 6);

WITH RECURSIVE
adj(u, v) AS (
  SELECT u, v FROM edge UNION SELECT v, u FROM edge
),
levels(node, depth) AS (
  SELECT 1, 0
  UNION
  SELECT a.v, levels.depth + 1
  FROM levels JOIN adj a ON a.u = levels.node
  WHERE levels.depth < (SELECT COUNT(DISTINCT n) FROM
    (SELECT u AS n FROM edge UNION SELECT v FROM edge))
)
SELECT '[' || GROUP_CONCAT(node, ', ') || ']'
FROM (
  SELECT node, MIN(depth) AS d
  FROM levels
  GROUP BY node
  ORDER BY d, node
);

Complexity

  • Time: O(V + E)
  • Space: O(V) for the visit set

Implementation notes

  • SQL: the input graph is staged in edge(u, v) and a CTE adj symmetrizes the relation. A WITH RECURSIVE levels(node, depth) CTE expands the BFS layer-by-layer; the UNION (not UNION ALL) deduplicates (node, depth) rows, and the WHERE levels.depth < (SELECT COUNT(DISTINCT n) ...) clause caps the recursion at the number of vertices so the BFS terminates on a connected component even when cycles let nodes be revisited at greater depths.
  • The final projection groups by node, picks MIN(depth) as the first-discovery distance, and orders by (d, node) so ties at the same depth are broken by ascending node id. That matches the canonical FIFO traversal order [1, 2, 3, 4, 5, 6] from the language-neutral spec.
  • A bare SELECT node FROM levels would emit duplicates from longer paths; the GROUP BY node collapses them so the printed order matches the imperative reference output exactly.
layer expansion At depth `d`, the visited set is exactly the nodes reachable in `d` edges. The next layer is every unvisited neighbour of a layer-`d` node.
first-discovery wins A node's BFS position is decided by the depth at which it is first reached; later, longer paths are ignored.