Learn Before
Activity (Process)

Breadth-First Search (BFS) on Graphs

Breadth-first search (BFS) is a deterministic graph-traversal algorithm that, given a graph G=(V,E)G = (V, E) and a source vertex ss (or a set of source vertices), visits every vertex reachable from the source(s) in non-decreasing order of hop-distance (number of edges traversed). It maintains a FIFO queue of frontier vertices: it dequeues the next vertex, marks it visited, and enqueues each of its unvisited neighbors, so vertices at distance dd are fully expanded before any vertex at distance d+1d+1. The output is a BFS tree rooted at the source(s), and for every visited vertex vv the algorithm yields the shortest unweighted-edge distance from the nearest source to vv. Because the order of expansion is determined by the queue discipline and the graph structure, two runs on the same graph and source set produce the same traversal order and the same set of explored paths up to any cutoff depth dd, which is what makes BFS deterministic and reproducible. The procedure extends to multi-source BFS by initializing the queue with all source vertices at distance 00 before the main loop, and to directed graphs by following only out-edges (or only in-edges, to obtain an 'upward' traversal in a DAG).

0

1

Updated 2026-05-18

Contributors are:

Who are from:

Tags

Science

Auditable Strict-Parity Evaluation of Prerequisite-Graph Retrieval for RAG under Leakage Controls

Related