BFS
(graph/bfs.hpp)

View this file on GitHub
Last update: 2026-08-13 01:41:40+09:00
Include: #include "graph/bfs.hpp"

Overview

Breadth-first search computes shortest paths in an unweighted graph, where every edge has the same cost. It expands vertices in increasing distance order: first the source, then all vertices one edge away, then all vertices two edges away, and so on.

Use BFS when the answer is measured by the number of edges, not by edge weights. For weighted shortest paths, use Dijkstra or Bellman-Ford instead.

Graph Orientation

Direction is respected. bfs works on directed graphs as written, and also on undirected graphs built with add_edge.

How to Use It

Call bfs(g, s) for one source, or bfs(g, sources) when several vertices should start at distance 0. Multi-source BFS is useful for problems like “distance to the nearest special vertex”.

The callback overloads invoke a callback exactly once when a vertex is discovered. Sources are reported in the supplied order, followed by other vertices in queue-insertion order, so callback distances are nondecreasing. They still return the complete BfsResult. The callback must not mutate the graph.

The primary callback signature is:

callback(int vertex, int parent);

parent is the BFS-tree parent of vertex, or -1 when vertex is a source. For convenience, callback(int vertex) is also accepted when parent information is not needed.

The result contains these members:

Member	Type / Signature	Meaning
`dist`	`std::vector<int>`	`dist[v]` is the number of edges from the nearest source to `v`, or `-1` if unreachable.
`parent`	`std::vector<int>`	`parent[v]` is the previous vertex on the restored BFS tree path, or `-1` for a source/unreachable vertex.
`parent_edge`	`std::vector<int>`	`parent_edge[v]` is the edge id used to enter `v`, or `-1`.
`reachable`	`bool reachable(int v) const`	Returns whether `v` was reached.
`path`	`std::vector<int> path(int t) const`	Restores one shortest path from a source to `t`. Requires `reachable(t)`.

Functions

Function	Signature	Description	Complexity
`bfs`	`template <class T> BfsResult bfs(const Graph<T>& g, int s)`	Runs BFS from one source.	$O(N + M)$
`bfs`	`template <class T> BfsResult bfs(const Graph<T>& g, const std::vector<int>& sources)`	Runs multi-source BFS.	$O(N + M)$
`bfs`	`template <class T, class Callback> BfsResult bfs(const Graph<T>& g, int source, Callback&& callback)`	Runs single-source BFS and invokes the callback on discovery.	$O(N + M + RF)$
`bfs`	`template <class T, class Callback> BfsResult bfs(const Graph<T>& g, const std::vector<int>& sources, Callback&& callback)`	Runs multi-source BFS and invokes the callback on discovery.	$O(N + M + RF)$

Here, R is the number of reached vertices and F is the cost of one callback.

Example

#include "graph/bfs.hpp"
#include "graph/graph.hpp"
#include <cassert>
#include <iostream>
#include <vector>

int main() {
    m1une::graph::Graph<> g(4);
    g.add_edge(0, 1);
    g.add_edge(1, 2);
    g.add_edge(0, 3);

    std::vector<int> discovered;
    auto res = m1une::graph::bfs(
        g,
        0,
        [&](int vertex, int parent) {
            discovered.push_back(vertex);
            if (vertex == 0) assert(parent == -1);
        }
    );
    std::cout << res.dist[2] << "\n";  // 2

    for (int v : res.path(2)) {
        std::cout << v << " ";         // 0 1 2
    }
    std::cout << "\n";
}

Depends on

Graph (graph/graph.hpp)

Required by

Verified with

Code

#ifndef M1UNE_GRAPH_BFS_HPP
#define M1UNE_GRAPH_BFS_HPP 1

#include <algorithm>
#include <cassert>
#include <concepts>
#include <functional>
#include <queue>
#include <utility>
#include <vector>

#include "graph.hpp"

namespace m1une {
namespace graph {

struct BfsResult {
    std::vector<int> dist;
    std::vector<int> parent;
    std::vector<int> parent_edge;

    bool reachable(int v) const {
        assert(0 <= v && v < int(dist.size()));
        return dist[v] != -1;
    }

    std::vector<int> path(int t) const {
        assert(reachable(t));
        std::vector<int> result;
        for (int v = t; v != -1; v = parent[v]) result.push_back(v);
        std::reverse(result.begin(), result.end());
        return result;
    }
};

namespace bfs_detail {

template <class Callback>
concept BfsCallback =
    std::invocable<Callback&, int, int> ||
    std::invocable<Callback&, int>;

template <BfsCallback Callback>
void invoke_callback(Callback& callback, int vertex, int parent) {
    if constexpr (std::invocable<Callback&, int, int>) {
        std::invoke(callback, vertex, parent);
    } else {
        std::invoke(callback, vertex);
    }
}

template <class T, class Callback>
BfsResult run_bfs(
    const Graph<T>& g,
    const std::vector<int>& sources,
    Callback& callback
) {
    int n = g.size();
    BfsResult result;
    result.dist.assign(n, -1);
    result.parent.assign(n, -1);
    result.parent_edge.assign(n, -1);

    std::queue<int> que;
    for (int s : sources) {
        assert(0 <= s && s < n);
        if (result.dist[s] != -1) continue;
        result.dist[s] = 0;
        invoke_callback(callback, s, -1);
        que.push(s);
    }

    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (const auto& e : g[v]) {
            if (!e.alive) continue;
            if (result.dist[e.to] != -1) continue;
            result.dist[e.to] = result.dist[v] + 1;
            result.parent[e.to] = v;
            result.parent_edge[e.to] = e.id;
            invoke_callback(callback, e.to, v);
            que.push(e.to);
        }
    }

    return result;
}

}  // namespace bfs_detail

template <class T>
BfsResult bfs(const Graph<T>& g, const std::vector<int>& sources) {
    auto callback = [](int) {};
    return bfs_detail::run_bfs(g, sources, callback);
}

template <class T>
BfsResult bfs(const Graph<T>& g, int s) {
    return bfs(g, std::vector<int>{s});
}

template <class T, class Callback>
requires bfs_detail::BfsCallback<Callback>
BfsResult bfs(
    const Graph<T>& g,
    const std::vector<int>& sources,
    Callback&& callback
) {
    return bfs_detail::run_bfs(g, sources, callback);
}

template <class T, class Callback>
requires bfs_detail::BfsCallback<Callback>
BfsResult bfs(const Graph<T>& g, int source, Callback&& callback) {
    return bfs(
        g,
        std::vector<int>{source},
        std::forward<Callback>(callback)
    );
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_BFS_HPP

#line 1 "graph/bfs.hpp"



#include <algorithm>
#include <cassert>
#include <concepts>
#include <functional>
#include <queue>
#include <utility>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 13 "graph/bfs.hpp"

namespace m1une {
namespace graph {

struct BfsResult {
    std::vector<int> dist;
    std::vector<int> parent;
    std::vector<int> parent_edge;

    bool reachable(int v) const {
        assert(0 <= v && v < int(dist.size()));
        return dist[v] != -1;
    }

    std::vector<int> path(int t) const {
        assert(reachable(t));
        std::vector<int> result;
        for (int v = t; v != -1; v = parent[v]) result.push_back(v);
        std::reverse(result.begin(), result.end());
        return result;
    }
};

namespace bfs_detail {

template <class Callback>
concept BfsCallback =
    std::invocable<Callback&, int, int> ||
    std::invocable<Callback&, int>;

template <BfsCallback Callback>
void invoke_callback(Callback& callback, int vertex, int parent) {
    if constexpr (std::invocable<Callback&, int, int>) {
        std::invoke(callback, vertex, parent);
    } else {
        std::invoke(callback, vertex);
    }
}

template <class T, class Callback>
BfsResult run_bfs(
    const Graph<T>& g,
    const std::vector<int>& sources,
    Callback& callback
) {
    int n = g.size();
    BfsResult result;
    result.dist.assign(n, -1);
    result.parent.assign(n, -1);
    result.parent_edge.assign(n, -1);

    std::queue<int> que;
    for (int s : sources) {
        assert(0 <= s && s < n);
        if (result.dist[s] != -1) continue;
        result.dist[s] = 0;
        invoke_callback(callback, s, -1);
        que.push(s);
    }

    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (const auto& e : g[v]) {
            if (!e.alive) continue;
            if (result.dist[e.to] != -1) continue;
            result.dist[e.to] = result.dist[v] + 1;
            result.parent[e.to] = v;
            result.parent_edge[e.to] = e.id;
            invoke_callback(callback, e.to, v);
            que.push(e.to);
        }
    }

    return result;
}

}  // namespace bfs_detail

template <class T>
BfsResult bfs(const Graph<T>& g, const std::vector<int>& sources) {
    auto callback = [](int) {};
    return bfs_detail::run_bfs(g, sources, callback);
}

template <class T>
BfsResult bfs(const Graph<T>& g, int s) {
    return bfs(g, std::vector<int>{s});
}

template <class T, class Callback>
requires bfs_detail::BfsCallback<Callback>
BfsResult bfs(
    const Graph<T>& g,
    const std::vector<int>& sources,
    Callback&& callback
) {
    return bfs_detail::run_bfs(g, sources, callback);
}

template <class T, class Callback>
requires bfs_detail::BfsCallback<Callback>
BfsResult bfs(const Graph<T>& g, int source, Callback&& callback) {
    return bfs(
        g,
        std::vector<int>{source},
        std::forward<Callback>(callback)
    );
}

}  // namespace graph
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

BFS
(graph/bfs.hpp)

Overview

Graph Orientation

How to Use It

Functions

Example

Depends on

Required by

Verified with

Code

BFS (graph/bfs.hpp)

Overview

Graph Orientation

How to Use It

Functions

Example

Depends on

Required by

Verified with

Code

BFS
(graph/bfs.hpp)