Skip to main content
Definition Website Computer and Technology

Breadth-First Search

Subject: Computer and Technology noun /ˈbrɛdθˌfɜːrst ˈsɜːrtʃ/ 1 definition

  1. Definition (noun)

    Entry #52 · Updated

    Breadth-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_104 and enqueuing all 1st-degree friends at depth 1 before inspecting any 2nd-degree friends at depth 2. When the queue reaches user_892 at depth 3, the search stops immediately and returns the three-hop connection chain, guaranteed to be minimal because all shorter paths were already checked.