Breadth-First Search

Traverse the graph in breadth-first order from a source node

Category: pathfinding

Syntax

SELECT * FROM graph_bfs(table_name, source_id [, max_depth])

Description

Breadth-first search (BFS) traverses a graph layer by layer starting from a specified source node. It discovers all nodes at distance 1 (direct neighbors) before moving to distance 2, then distance 3, and so on. This level-order traversal guarantees that each node is reached via the shortest hop-count path from the source. BFS is fundamental for computing unweighted shortest paths, measuring graph diameter, and exploring node neighborhoods up to a specified depth. The function loads edge data from a registered Delta table into a Compressed Sparse Row (CSR) representation. The traversal begins at the specified source_id and proceeds outward using a queue-based frontier expansion. Each discovered node records its distance from the source and its parent in the BFS spanning tree. Column names for source and target are auto-detected from standard conventions (src/source/src_id, dst/target/dst_id). If the source_id does not exist in the graph, an empty result set is returned. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges reachable from the source. When max_depth is specified, only the portion of the graph within that many hops is visited, which can significantly reduce computation for large graphs. BFS is the most efficient algorithm for unweighted shortest-path queries. GPU acceleration is not currently available for BFS. All computation runs on the CPU. The graph cache (256 MB default budget, LRU eviction, 10-minute idle timeout) retains the CSR topology, so repeated BFS calls from different source nodes on the same table reuse the cached graph without reloading.

Parameters

Name	Type	Description
`table_name`		Specify the name of the registered Delta table containing edge data. The table must include source and target columns (auto-detected as src/source/src_id and dst/target/dst_id). Edge weights are ignored; BFS treats all edges as having unit cost.
`source_id`		Specify the node ID from which to start the breadth-first traversal. This must be a valid node ID present in the edge table. If the node ID does not exist in the graph, an empty result set is returned.
`max_depth`		Set the maximum traversal depth (number of hops from the source). Default is unlimited, meaning the entire reachable graph is traversed. Set a lower value (e.g., 2 or 3) to restrict results to the immediate neighborhood of the source node. Valid range is 1 or greater.

Examples

CREATE TABLE road_network AS
SELECT * FROM VALUES
  (1, 2, 1.0),
  (1, 3, 1.0),
  (2, 4, 1.0),
  (3, 4, 1.0),
  (4, 5, 1.0),
  (5, 6, 1.0)
AS t(src, dst, weight);

SELECT * FROM graph_bfs('road_network', 1);

SELECT node_id, distance
FROM graph_bfs('road_network', 1, 2);

-- BFS guarantees shortest hop-count paths; trace parent_id chain
SELECT node_id, distance, parent_id
FROM graph_bfs('road_network', 1)
ORDER BY distance;

SELECT distance, COUNT(*) AS node_count
FROM graph_bfs('road_network', 1)
GROUP BY distance
ORDER BY distance;

SELECT b.node_id, b.distance, n.name
FROM graph_bfs('road_network', 1, 3) b
JOIN locations n ON b.node_id = n.id
ORDER BY b.distance, n.name;

Pitfalls

BFS treats every edge as unit-cost. It computes shortest hop count, not weighted shortest paths. For weighted shortest paths, use graph_shortest_path instead; using BFS on a weighted graph silently ignores the weight column.
The source node is returned with distance 0 and parent_id NULL. Downstream joins must handle the NULL parent explicitly; unconditional joins on parent_id drop the source row.
An invalid or absent source_id returns an empty result set with no error. Always verify the source exists in the graph before relying on result cardinality (for example by joining graph_bfs against a DISTINCT node set).
Traversal follows edge direction. Directed edges are not traversed in reverse, so a node that is reachable only through incoming edges will not appear in the result. Materialise reverse edges into the source table when bidirectional exploration is required.
GPU acceleration is not available for BFS. The ON GPU execution hint is silently ignored, so latency characteristics differ from GPU-accelerated centrality or community functions.
max_depth caps both the traversal horizon and the distance column value. A caller expecting complete reachability must omit max_depth; a caller expecting bounded results must supply it. There is no 'deep enough' sentinel to distinguish the two cases post-hoc.