Breadth-First Search
Subject: Computer and Technology noun /ˈbrɛdθˌfɜːrst ˈsɜːrtʃ/ 1 definition
- graph-algorithms
- search-algorithms
- graph-traversal
- computer-science
-
Definition (noun)
Entry #52 · UpdatedBreadth-First Search (BFS) is a graph and tree traversal algorithm that systematically explores vertices in expanding layers outward from a chosen starting node, visiting every neighbor at the current depth before advancing to nodes one edge farther away. Using a first-in, first-out (FIFO) queue and a visited-state tracker to avoid revisiting vertices in cyclic graphs, it processes each reachable vertex and edge once in O(V + E) time when represented with adjacency lists. Because it expands uniformly by hop count rather than plunging down individual branches like depth-first search, BFS guarantees the shortest path by edge count in unweighted graphs, whereas graphs with varying edge weights require cost-aware algorithms such as Dijkstra's.
Common Forms
Standard Single-Source BFS: Starts from one origin vertex using a FIFO queue and a visited set to compute minimum hop distances or locate the nearest target node across an unweighted graph.
Level-Order Tree Traversal: Applies BFS to rooted trees without needing a visited tracker—since trees contain no cycles—to visit and process nodes row by row from the root downward.
Multi-Source BFS: Initializes the queue with multiple starting vertices at depth zero simultaneously so search frontiers expand in parallel to find each node's shortest distance to the nearest source.
Bidirectional BFS: Runs two simultaneous searches—forward from the start node and backward from the goal node—and stops as soon as their frontiers intersect, drastically reducing the number of explored vertices in large graphs.
Example
A social networking service computes the degrees of separation between two profiles by starting a BFS from
user_104and enqueuing all 1st-degree friends at depth 1 before inspecting any 2nd-degree friends at depth 2. When the queue reachesuser_892at depth 3, the search stops immediately and returns the three-hop connection chain, guaranteed to be minimal because all shorter paths were already checked.