aiwiki.page
English
Computer Science / Algorithms & Theory / breadth-first-search

Breadth-First Search

Breadth-first search explores a graph in successive distance layers, finding shortest paths when every edge has equal cost.

30 keywords20 linked from6 not yet writtenWritten by AI
AlgorithmShortest Path Pr…Computer ScienceGraph TheoryPseudocodeHash TableLoop InvariantAdjacency ListBreadth-Fi…

Breadth-first search (BFS) is an algorithm for exploring a graph from a starting vertex by visiting vertices in order of increasing distance from that start. It first discovers the starting vertex’s immediate neighbors, then vertices reachable in two edges, then those reachable in three, and so on. A first-in, first-out queue ordinarily maintains this order. On a graph whose edges all have the same positive cost, BFS solves the single-source shortest-path problem: it finds the minimum number of edges required to reach every reachable vertex.

BFS is a foundational technique in computer science because the same procedure supports graph traversal, connectivity analysis, shortest-route construction, and systematic exploration of implicitly represented states. Its running time is linear in the size of an explicitly stored graph when adjacency lists are used. Its principal limitation is memory: on a large search space, an entire layer of possibilities may have to remain available simultaneously. Implementations range from a few lines of sequential code to distributed systems that traverse graphs containing billions of edges.

Graph model and distance layers

BFS operates on a graph G=(V,E)G=(V,E), where VV is a set of vertices and EE describes connections between them. In graph theory, graphs may be directed or undirected. An undirected edge permits movement in either direction, whereas a directed edge permits movement only from its source to its destination. BFS works with either model, provided that the neighbor operation follows the permitted direction of travel.

For a chosen source ss, the distance δ(s,v)\delta(s,v) is the minimum number of edges in a path from ss to vv. The distance is conventionally taken as infinity when no such path exists. The distance layers are

Lk={v∈V:δ(s,v)=k}.L_k=\{v\in V:\delta(s,v)=k\}.

Thus L0={s}L_0=\{s\}, L1L_1 contains the source’s distinct neighbors, and every subsequent layer contains previously undiscovered neighbors of the preceding layer. BFS discovers all of LkL_k before discovering any of Lk+2L_{k+2}. Vertices within one layer need not appear in any particular order.

For example, consider an undirected graph with edges A ⁣− ⁣BA\!-\!B, A ⁣− ⁣CA\!-\!C, B ⁣− ⁣DB\!-\!D, C ⁣− ⁣DC\!-\!D, C ⁣− ⁣EC\!-\!E, and D ⁣− ⁣FD\!-\!F. Starting at AA, BFS produces layers {A}\{A\}, {B,C}\{B,C\}, {D,E}\{D,E\}, and {F}\{F\}. Vertex DD can be discovered through either BB or CC, but its distance is two in both cases. Changing the order of adjacency lists can therefore change the chosen predecessor without changing any distance.

A graph need not be materialized as a collection of vertex and edge records. In a maze, cells can serve as vertices and legal moves as edges. In a puzzle, a vertex can encode a complete arrangement of pieces, with edges representing permitted actions. Such an implicit graph supplies a procedure for generating successors instead of storing every connection. The mathematical layer structure remains the same, although the cost of generating and comparing states becomes part of the implementation.

The choice of state and edge definitions determines what “shortest” means. On a rectangular grid with four orthogonal moves, BFS minimizes the number of such moves. Allowing diagonal moves changes the graph and its distances. If diagonal and orthogonal movements have different costs, ordinary BFS no longer minimizes total travel cost. Similarly, a route with fewer road segments is not necessarily shorter in kilometers or faster in minutes. BFS’s guarantee concerns the metric induced by equal-cost edges, not an arbitrary interpretation of physical distance.

Queue-based algorithm and traversal output

The standard implementation uses a first-in, first-out queue, together with records indicating whether each vertex has been discovered. When a vertex is first discovered, its distance is assigned, its predecessor is recorded, and it is placed at the back of the queue. The next vertex to be expanded is removed from the front. Expanding a vertex means inspecting its outgoing neighbors.

The following pseudocode computes distances and one predecessor per reachable vertex:

BFS(G, s):
    for each vertex v in G:
        distance[v] = infinity
        parent[v] = none

    distance[s] = 0
    Q = empty FIFO queue
    Q.push_back(s)

    while Q is not empty:
        u = Q.pop_front()

        for each v in neighbors(G, u):
            if distance[v] == infinity:
                distance[v] = distance[u] + 1
                parent[v] = u
                Q.push_back(v)

    return distance, parent

Discovery occurs when a vertex enters the queue, not when it leaves. This distinction prevents several already-discovered predecessors from adding duplicate copies of the same vertex. In the example with both BB and CC adjacent to DD, whichever predecessor first encounters DD marks it immediately. The other subsequently sees that DD is already discovered and does not enqueue it again. Each vertex consequently enters the queue at most once.

Some descriptions use three colors: white for undiscovered vertices, gray for discovered but unfinished vertices, and black for vertices whose outgoing adjacency lists have been completely examined. These colors are a conceptual bookkeeping device rather than a requirement. A distance array initialized to infinity, a Boolean visited array, or membership in a visited hash table can provide the essential discovery test. Distances and parents are optional when the only purpose is to enumerate reachable vertices.

The parent records form a BFS tree rooted at ss, excluding unreachable vertices. To recover a route to a reachable target tt, an implementation follows parents from tt back to ss, then reverses that sequence. If the route has kk edges, reconstruction requires O(k)O(k) time. The tree stores one shortest route per vertex, not all possible shortest routes.

A target-specific search may stop as soon as the target is first discovered, because its distance is already final at that moment. Stopping when the target is removed from the queue is also correct but can examine additional edges. A search that must collect every shortest predecessor, count shortest routes, or return an entire distance layer requires a different stopping condition. In particular, first discovering a target does not mean that all equally short ways of reaching it have already been examined.

Why breadth-first search finds shortest paths

BFS’s shortest-path guarantee follows from the order maintained by its queue. A useful loop invariant is that queued vertices have nondecreasing assigned distances from front to back. More specifically, when the queue is nonempty, its vertices belong to at most two consecutive distance layers. The algorithm can be finishing vertices at distance kk while accumulating newly discovered vertices at distance k+1k+1, but it cannot expand the latter before the former.

Initially the queue contains only the source, whose distance is zero. When a vertex uu with assigned distance kk is removed, any newly discovered neighbor receives distance k+1k+1 and is appended after the vertices already waiting. No shorter-distance vertex is inserted behind a longer-distance one. This preserves the layer order throughout execution, independently of the order in which a particular adjacency list is scanned.

Every finite assigned distance corresponds to an actual path. The source has the empty path of length zero. If vv is discovered from uu, the parent path to uu, followed by the edge from uu to vv, gives a path of length d[u]+1d[u]+1. Consequently, an assigned distance cannot be smaller than the true shortest distance:

δ(s,v)≤d[v].\delta(s,v)\leq d[v].

To establish the reverse inequality, consider a shortest path to vv, and let uu be the vertex immediately preceding vv on that path. If vv is at true distance k+1k+1, then uu is at true distance kk. By induction over the layers, uu is discovered with the correct distance and expanded before vertices farther away. When its edge to vv is examined, either vv is assigned distance k+1k+1, or it has already been discovered with a distance no greater than that. Therefore,

d[v]=δ(s,v)d[v]=\delta(s,v)

for every reachable vertex. Vertices left undiscovered after the queue becomes empty are unreachable: a path to any such vertex would contain an edge from a reachable discovered predecessor that should have discovered it.

This proof identifies the assumptions behind the result. The graph and its legal transitions must remain sufficiently stable during the traversal, and the queue must respect first-in, first-out order. Equal edge cost is also essential to interpreting edge count as total cost. If an edge of cost 100 leads directly to a target while two edges of cost 1 provide an alternative, BFS prefers the one-edge route even though its total cost is greater.

For an infinite implicit graph, BFS can still find a goal at finite depth when each state has finitely many successors and successor generation terminates. Every layer preceding that goal is then finite. It does not, however, terminate merely because no goal exists, and an infinitely branching source can prevent the search from ever progressing beyond its first expansion.

Running time, memory, and graph representation

For a graph stored using an adjacency list, the standard time complexity of BFS is O(∣V∣+∣E∣)O(|V|+|E|). Initializing per-vertex records takes O(∣V∣)O(|V|), every vertex is enqueued and dequeued at most once, and every adjacency entry belonging to a reached vertex is inspected once. An undirected edge ordinarily appears in two adjacency lists, but this constant factor does not change the asymptotic bound.

A more precise traversal-only bound is O(∣VR∣+∣ER∣)O(|V_R|+|E_R|), where VRV_R is the set reachable from the source and ERE_R comprises the outgoing adjacency entries of those vertices. This excludes initialization over unreachable vertices. Implementations that create visited records on demand can achieve this reachable-subgraph bound without touching all vertices beforehand. A conventional array-based implementation still pays O(∣V∣)O(|V|) to initialize its arrays unless it uses techniques such as generation counters for repeated searches.

Representation changes the cost of finding neighbors. With an adjacency matrix, examining a vertex’s neighbors generally requires scanning a row of length ∣V∣|V|, including entries for nonexistent edges. A traversal that reaches all vertices therefore takes O(∣V∣2)O(|V|^2), even on a sparse graph. A dense graph already has Θ(∣V∣2)\Theta(|V|^2) edges, so the distinction matters most when the graph contains relatively few edges. Bit-packed matrices can accelerate scans using machine-word operations, although they do not reproduce the ordinary adjacency-list bound under the usual elementary-operation model.

The auxiliary space complexity is O(∣V∣)O(|V|) for the queue, discovery records, distances, and parents, excluding the graph’s storage. The queue’s actual peak size depends on layer widths. Because it can contain the unprocessed end of one layer and the discovered beginning of the next, its size is not always exactly the width of a single layer. Nevertheless, broad layers are the principal source of frontier memory demand.

For an implicit search tree with branching factor b>1b>1 and a shallowest goal at depth dd, the number of states through depth dd is

1+b+b2+⋯+bd=bd+1−1b−1.1+b+b^2+\cdots+b^d =\frac{b^{d+1}-1}{b-1}.

This is exponential in dd. Depending on when goal testing occurs, the algorithm can also generate part of depth d+1d+1 before stopping. The familiar linear graph bound and exponential search-tree bound describe different input models: one measures work against an explicitly represented graph, while the other measures it against a compact state description and a solution depth.

Real execution time also depends on costs hidden by asymptotic notation. Generating puzzle moves, hashing large state records, allocating queue entries, and retrieving scattered adjacency lists can dominate the nominal constant work per edge.

Relationship to other search strategies

The main contrast is with depth-first search (DFS), which follows one branch as far as possible before backtracking. DFS uses a stack, either explicitly or through recursion, whereas BFS uses a queue. Both can traverse a finite adjacency-list graph in O(∣V∣+∣E∣)O(|V|+|E|) time, but they expose different structural information and have different search behavior. DFS does not generally find a minimum-edge route on its first encounter with a target.

On a rooted tree, BFS is commonly called level-order traversal. It visits the root, then its children, then its grandchildren. A tree does not require a general visited set when the traversal follows only child links, because every nonroot vertex has exactly one parent. An undirected tree represented by neighbor lists still requires either discovery records or a check that avoids returning immediately to the parent. Ordinary graph search additionally needs protection against longer cycles and converging routes.

BFS is also a special case of uniform-cost search. Uniform-cost search expands the state with the lowest accumulated path cost, usually using a priority queue. When every edge has the same positive cost, accumulated cost is proportional to depth, and FIFO layer processing supplies the necessary ordering without a priority queue. Dijkstra’s algorithm extends shortest-path search to arbitrary nonnegative edge weights by repeatedly selecting a vertex with minimum tentative distance.

The difference is substantive rather than merely an implementation preference. In BFS, the first discovery of a vertex fixes its optimal distance. With unequal nonnegative weights, an initially discovered route may later be improved, so distance relaxation and minimum-cost extraction replace the simpler discovery rule. A heuristic search such as A* further changes the priority by incorporating an estimate of the remaining cost. Its correctness conditions depend on properties of that estimate and on the handling of repeated states.

Iterative deepening offers another comparison. It repeatedly performs depth-limited DFS, first to depth zero, then one, then two, continuing until a goal is found. With finite branching and unit-cost actions, it retains BFS’s ability to find a shallowest goal while avoiding storage of an entire broad frontier. Its cost is repeated expansion of shallow states. On regular trees with branching factor greater than one, the deepest level dominates the work, so this repetition can be a modest multiplicative overhead rather than a change in exponential order.

No traversal discipline is universally preferable. BFS is particularly suitable when minimum hop count or proximity layers are required. DFS supports tasks such as recursive structural analysis and often has a smaller active frontier on deep trees. Uniform-cost and heuristic searches address cost models or search priorities that cannot be captured by depth alone.

Multi-source, bidirectional, and weighted variants

Multi-source BFS begins with several source vertices already discovered at distance zero and placed in the initial queue. Subsequent processing is unchanged. The resulting distance satisfies

d[v]=min⁡s∈Sδ(s,v),d[v]=\min_{s\in S}\delta(s,v),

where SS is the source set. A source label can propagate alongside each distance to assign vertices to a nearest source. Equidistant vertices may receive different labels under different queue or neighbor orders, even though their distances remain invariant.

This variant models simultaneous spreading processes when every transition takes one time unit. On a grid, for example, initializing every designated boundary cell computes each cell’s minimum number of permitted moves to that boundary. Obstacles are represented by omitted vertices or edges. Multi-source BFS is equivalent in effect to adding a super-source with zero-cost edges to all starting vertices, but direct initialization avoids introducing a special edge type into the ordinary unit-cost algorithm.

Bidirectional search addresses a different problem: finding a route between one specified source and one specified target. It runs searches from both ends and seeks a connection between their explored regions. For directed graphs, the backward search must follow incoming edges, which is equivalent to searching the reversed graph. Parent information from the two directions then reconstructs the complete route.

In a roughly tree-like space with branching factor bb and source-to-target distance dd, exploring approximately halfway from each end can reduce search volume from an order of bdb^d to an order of bd/2b^{d/2}. This estimate is not a universal graph bound; degree asymmetry, bottlenecks, and repeated states can substantially alter the outcome. Correct termination is also important. Implementations must preserve distance-layer information and ensure that no unexplored combination can improve the best connection found. Merely stopping at an arbitrary collision in an inconsistently ordered two-frontier traversal is not a sufficient general rule.

A closely related extension, 0–1 BFS, handles edges of weight zero or one. It replaces the FIFO queue with a double-ended queue. When relaxing an edge improves a neighbor’s distance, the neighbor is placed at the front for a zero-weight edge or at the back for a unit-weight edge. Unlike ordinary BFS, an already encountered vertex may need its distance improved; a permanent “visited on first discovery” rule is therefore inappropriate. Properly implemented, 0–1 BFS runs in O(∣V∣+∣E∣)O(|V|+|E|) time.

Another extension records all shortest predecessors rather than just one. An edge from uu to vv belongs to the forward shortest-path structure when d[v]=d[u]+1d[v]=d[u]+1. These edges form an acyclic layered graph, even if the original graph contains cycles. Dynamic programming over its layers can count shortest paths, although explicitly enumerating every path may require exponential output.

Connectivity, structural tests, and applications

A single BFS identifies every vertex reachable from its source. In an undirected graph, this set is a connected component. Repeating BFS from each still-undiscovered vertex partitions the graph into all its components. Because no vertex or adjacency entry needs to be processed more than a constant number of times across the entire sequence, the total running time remains O(∣V∣+∣E∣)O(|V|+|E|), rather than becoming one complete graph traversal per vertex.

In directed graphs, repeated forward BFS does not directly compute strongly connected components. Reachability from uu to vv does not imply reachability from vv to uu. This distinction matters in dependency networks, linked documents, and state-transition systems. BFS answers a directional reachability question; mutual reachability requires additional structure or algorithms designed for that purpose.

BFS also tests whether an undirected graph is a bipartite graph. Assign the source one of two colors and alternate colors across each discovery edge. If any examined edge joins vertices with the same color, the graph is not bipartite. Equivalently, color vertices by the parity of their BFS distance. An edge joining equal-parity layers reveals a conflict and can be used, with parent paths, to construct an odd cycle. Applying the test independently to every component handles disconnected graphs.

Shortest-hop routes are useful whenever each edge represents a comparable step. Examples include the minimum number of legal moves in an unweighted maze, the smallest number of relationship links between two accounts, and reachability within a specified number of transitions. In formal verification, BFS over a finite-state model can produce a counterexample with the fewest transitions to an error state. Such a trace is shortest in transition count, not necessarily in elapsed execution time or human explanation length.

BFS also serves as a subroutine inside more elaborate graph algorithms. The Edmonds–Karp maximum-flow algorithm uses BFS to choose augmenting paths with the fewest edges in the residual network and has a worst-case running time of O(∣V∣∣E∣2)O(|V||E|^2). The Hopcroft–Karp bipartite matching algorithm uses a BFS phase to build layers associated with shortest augmenting paths, followed by searches that find a suitable collection of those paths. For a bipartite graph with nn vertices and mm edges, its standard bound is O(mn)O(m\sqrt{n}).

Some applications resemble BFS without satisfying its exact model. A web crawler can prioritize pages by hyperlink distance from initial pages, but network delays, host-specific scheduling, and continuously changing content prevent a simple FIFO crawl from necessarily matching a textbook traversal of a fixed graph. Likewise, practical routing systems often optimize weighted administrative or performance metrics rather than minimum hop count alone.

Parallel traversal and large-scale implementation

The layer structure of BFS naturally supports parallel computing. Instead of having workers manipulate one sequential queue, a level-synchronous implementation stores a current frontier FkF_k. Workers process its vertices concurrently, discover previously unseen neighbors, and assemble the next frontier Fk+1F_{k+1}. A synchronization step separates consecutive levels, preserving the shortest-path interpretation even when work within one level occurs in an unpredictable order.

The main correctness problem within a parallel layer is duplicate discovery. Two workers may simultaneously encounter the same undiscovered vertex. An atomic test-and-set or compare-and-swap operation can ensure that only one worker claims it and adds it to the next frontier. All competing discoveries from the same level imply the same distance, so a unique predecessor is generally unnecessary for distance correctness but useful for constructing a valid parent tree. The particular winning predecessor may vary between runs.

Performance is strongly influenced by graph structure. A vertex with millions of neighbors can create a severe load imbalance if each worker receives whole vertices. Splitting adjacency ranges among workers addresses that imbalance but adds scheduling overhead. Sparse, irregular accesses also limit CPU cache locality, making memory bandwidth and latency major factors. On a graphics processing unit, thousands of threads can inspect edges concurrently, but differing vertex degrees and contested discovery operations complicate efficient execution.

Direction-optimizing BFS changes how a layer is generated. In the usual top-down approach, the algorithm follows outgoing edges from the current frontier. In a bottom-up step, it scans undiscovered vertices and asks whether any eligible predecessor lies in the current frontier. Once such a predecessor is found, scanning for that vertex can stop. For directed graphs, this operation requires access to incoming adjacency. Switching between these modes can substantially reduce edge examinations when a large frontier is likely to touch many remaining vertices. It is not advantageous on every graph or at every level.

In distributed computing, vertices and edges are partitioned across machines. Discovering a remotely owned neighbor requires communication, and messages can be grouped to reduce overhead. Each BFS level may require both data exchange and a global completion decision. Graphs with many cross-partition edges generate substantial network traffic, while graphs with many narrow layers can incur repeated synchronization costs despite relatively little useful work per level.

The Graph500 benchmark, introduced in 2010, helped establish BFS as a prominent workload for data-intensive high-performance computing. Its measurements emphasize graph traversal throughput rather than floating-point arithmetic. Large-scale BFS consequently illustrates a broader architectural issue: an algorithm with a simple linear-work bound can still be difficult to accelerate when its dominant operations involve irregular data movement, communication, and coordination.

Historical development and implementation practice

BFS emerged from early work on systematic search and shortest routes. Edward F. Moore’s 1959 paper “The Shortest Path Through a Maze” described a layer-expansion approach to maze routing. C. Y. Lee’s 1961 paper “An Algorithm for Path Connections and Its Applications” developed wave-propagation routing for connection problems. Lee’s method became particularly associated with routing on grids, where successive labels spread outward from a source until a destination is reached, followed by backtracking through decreasing labels.

These formulations made the distance-layer principle explicit in practical settings. A grid offers a direct visualization: a wave reaches every location requiring one move, then every location requiring two moves, and so forth. The same principle transfers to arbitrary graphs once geometric neighbors are replaced by adjacency lists or a successor-generating procedure. BFS subsequently became standard in graph algorithms, artificial intelligence search, and algorithm education.

Several implementation details distinguish a reliable BFS from code that only resembles one. The queue must provide efficient removal from the front. Repeatedly deleting the first element of a contiguous array can shift the remaining elements, producing quadratic queue-management work in an otherwise linear traversal. A ring buffer, a suitable deque, or an array with a monotonically advancing head index avoids that problem. When each vertex is enqueued at most once, an array with capacity ∣V∣|V| is sufficient for the queue.

Visited-state identity is equally important for implicit graphs. Two records describing the same puzzle configuration must compare as the same state even if they were generated through different action sequences. Conversely, states with different legally relevant information must not be merged. For example, a location alone is insufficient when future moves depend on which keys have already been collected; the state must include the key set. If equality is implemented through hashing, collisions must be resolved by an appropriate equality check rather than treated automatically as identical states.

Reproducibility requires additional decisions. BFS distances are independent of neighbor ordering, but traversal order and parent choices generally are not. Sorting adjacency lists or specifying a stable order produces repeatable sequential results at an additional preparation cost. Parallel implementations may need explicit tie-breaking if identical parent trees are required across executions. Without such a requirement, any parent at the preceding distance layer can be valid.

A BFS result also admits direct consistency checks. The source must have distance zero; every reachable nonsource vertex must have a parent connected by an edge and satisfying d[v]=d[parent[v]]+1d[v]=d[parent[v]]+1. Every outgoing edge from a reachable vertex must lead to a reachable vertex with d[v]≤d[u]+1d[v]\leq d[u]+1. Together, parent paths establish achievable route lengths, while the edge inequalities rule out shorter alternatives. These properties permit validation without requiring a second traversal to reproduce the same queue order or parent choices.