Skip to content

bfs.md

Latest commit

 

History

History
300 lines (232 loc) · 9.54 KB

bfs.md

File metadata and controls

300 lines (232 loc) · 9.54 KB
graph-v3 logo

Breadth-First Search

← Back to Algorithm Catalog

Table of Contents

Overview

Breadth-first search explores vertices in level-order (FIFO) from one or more source vertices. It is entirely visitor-driven — the algorithm itself has no output arrays. Instead, you provide a visitor struct whose callback methods are invoked at each stage of the traversal.

BFS is the foundation for unweighted shortest paths, connected-component discovery, and level-based graph analysis.

The graph must satisfy adjacency_list<G> — both index-based (contiguous integer-indexed) and map-based (sparse vertex ID) graphs are supported.

Note: Unlike DFS, BFS does not classify edges (no tree/back/ forward edge events). If you need edge classification, use DFS instead.

When to Use

  • Unweighted shortest paths — BFS finds shortest hop-count distances in O(V+E), optimal for unweighted graphs.
  • Level-order traversal — vertices are visited in increasing order of distance from the source.
  • Connected components — start BFS from an unvisited vertex to discover its component (though the dedicated connected_components algorithm is more convenient).
  • Multi-source queries — start from multiple roots simultaneously to find nearest sources.

Not suitable when:

Include

#include <graph/algorithm/breadth_first_search.hpp>

Signatures

// Multi-source BFS
void breadth_first_search(G&& g, const Sources& sources,
    Visitor&& visitor = empty_visitor(),
    const Alloc& alloc = Alloc());

// Single-source BFS
void breadth_first_search(G&& g, const vertex_id_t<G>& source,
    Visitor&& visitor = empty_visitor(),
    const Alloc& alloc = Alloc());

Parameters

Parameter Description
g Graph satisfying adjacency_list
source / sources Source vertex ID or range of source vertex IDs
visitor Optional visitor struct with callback methods (see below). Default: empty_visitor{}.
alloc Allocator for internal queue storage. Default: std::allocator<std::byte>{}.

Visitor Events

BFS supports an optional visitor with the following callbacks. Each vertex event also has an _id variant that receives vertex_id_t<G> instead of a vertex reference (e.g., on_discover_vertex_id(g, uid)). You only need to define the events you care about — missing methods are silently skipped.

Event Called when
on_initialize_vertex(g, u) Before traversal, for each vertex during color initialization
on_discover_vertex(g, u) Vertex first reached (pushed into queue)
on_examine_vertex(g, u) Vertex popped from queue for processing
on_examine_edge(g, uv) Outgoing edge examined during vertex processing
on_finish_vertex(g, u) All adjacent edges of vertex explored

Supported Graph Properties

Directedness:

  • ✅ Undirected graphs
  • ✅ Directed graphs

Edge Properties:

  • ✅ Unweighted edges
  • ✅ Weighted edges (weights ignored)
  • ✅ Multi-edges (each edge triggers visitor events)
  • ✅ Self-loops (treated as normal edges for visitor events)

Graph Structure:

  • ✅ Connected graphs
  • ✅ Disconnected graphs (only reachable vertices visited)
  • ✅ Empty graphs (no-op)

Container Requirements:

  • Required: adjacency_list<G>
  • Sources: std::ranges::input_range with values convertible to vertex_id_t<G>

Examples

Example 1: Level-Order Traversal

Record the order in which vertices are discovered — this is always in non-decreasing order of distance from the source.

#include <graph/algorithm/breadth_first_search.hpp>
#include <graph/container/dynamic_graph.hpp>
#include <vector>

using Graph = container::dynamic_graph<void, void, void, uint32_t, false,
    container::vov_graph_traits<void>>;

//   0 → 1 → 3
//   ↓   ↓
//   2 → 3 → 4
Graph g({{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}});

struct DiscoveryOrder {
    std::vector<uint32_t>& order;
    void on_discover_vertex(const auto& g, const auto& u) {
        order.push_back(vertex_id(g, u));
    }
};

std::vector<uint32_t> order;
breadth_first_search(g, 0u, DiscoveryOrder{order});
// order = {0, 1, 2, 3, 4}  (level-order from vertex 0)
// Level 0: {0}, Level 1: {1, 2}, Level 2: {3}, Level 3: {4}

Example 2: Multi-Source BFS

Start BFS from multiple source vertices simultaneously — useful for nearest-facility queries or multi-root traversals.

struct DiscoveryOrder {
    std::vector<uint32_t>& order;
    void on_discover_vertex(const auto& g, const auto& u) {
        order.push_back(vertex_id(g, u));
    }
};

std::vector<uint32_t> order;
std::vector<uint32_t> sources = {0u, 4u};
breadth_first_search(g, sources, DiscoveryOrder{order});
// Both sources are discovered at level 0, then their neighbors at level 1, etc.

Example 3: Computing Distances (Unweighted)

BFS naturally computes shortest hop-count distances in unweighted graphs.

struct DistanceRecorder {
    std::vector<int>& dist;

    void on_examine_edge(const auto& g, const auto& uv) {
        auto uid = source_id(g, uv);
        auto vid = target_id(g, uv);
        if (dist[vid] < 0) {  // unvisited
            dist[vid] = dist[uid] + 1;
        }
    }
};

std::vector<int> dist(num_vertices(g), -1);
dist[0] = 0;  // source distance = 0
breadth_first_search(g, 0u, DistanceRecorder{dist});
// dist[v] = shortest hop count from vertex 0 to v, or -1 if unreachable

Example 4: Connected Component Discovery

Use BFS to discover all vertices in a component, then repeat for unvisited vertices to find all components of a disconnected graph.

// Disconnected graph: {0,1,2} and {3,4}
Graph g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {3, 4}, {4, 3}});

struct ComponentLabeler {
    std::vector<int>& component;
    int current_label;
    void on_discover_vertex(const auto& g, const auto& u) {
        component[vertex_id(g, u)] = current_label;
    }
};

size_t n = num_vertices(g);
std::vector<int> component(n, -1);
int label = 0;

for (uint32_t v = 0; v < n; ++v) {
    if (component[v] < 0) {
        breadth_first_search(g, v, ComponentLabeler{component, label});
        ++label;
    }
}
// component = {0, 0, 0, 1, 1}  — two components found
// For a dedicated algorithm, see connected_components.md

Example 5: Counting Events with a Visitor

Track how many times each event fires — useful for testing and debugging.

struct CountingVisitor {
    int initialized = 0, discovered = 0, examined = 0;
    int edges_examined = 0, finished = 0;

    void on_initialize_vertex(const auto&, const auto&) { ++initialized; }
    void on_discover_vertex(const auto&, const auto&)    { ++discovered; }
    void on_examine_vertex(const auto&, const auto&)     { ++examined; }
    void on_examine_edge(const auto&, const auto&)       { ++edges_examined; }
    void on_finish_vertex(const auto&, const auto&)      { ++finished; }
};

CountingVisitor vis;
breadth_first_search(g, 0u, vis);
// vis.discovered == num reachable vertices from source
// vis.edges_examined == num edges explored
// vis.finished == vis.examined == vis.discovered (every discovered vertex
//   is eventually examined and finished)

Mandates

  • G must satisfy adjacency_list<G>
  • Sources must be std::ranges::input_range with values convertible to vertex_id_t<G> (multi-source overload)
  • Visitor callbacks (if present) must accept appropriate graph and vertex/edge parameters

Preconditions

  • All vertex IDs in sources must be valid vertex IDs in g
  • g must not be modified during traversal
  • Visitor methods must not modify graph structure
  • Duplicate sources are allowed — each duplicate causes an extra discovery event

Effects

  • Does not modify the graph g
  • Invokes visitor callbacks in BFS traversal order
  • Vertices are visited in level-order (distance from sources)
  • All vertices reachable from any source are visited exactly once

Throws

  • std::bad_alloc if internal allocations fail
  • Exception guarantee: Basic. Graph g remains unchanged; output may be partial.

Complexity

Metric Value
Time O(V + E)
Space O(V) for the visited array and queue

See Also