01-BFS
(graph/bfs01.cpp)

• View this file on GitHub
• Last update: 2026-03-12 00:49:33+09:00

説明

辺重みが 0 または 1 のグラフで単一始点最短路を求める。 計算量は $O(V + E)$。

できること

• vector<T> bfs01(int s, vector<vector<edge<T>>>& G) 始点 s から各頂点への最短距離を返す
• 到達不能な頂点 INF<T> のまま返す

使い方

#include "../graph/bfs01.cpp" を読み込む。 隣接リスト G を作り、各辺のコストに 0 か 1 を入れて bfs01(s, G) を呼ぶ。

vector<vector<edge<int>>> G(n);
G[u].emplace_back(v, 0);
G[v].emplace_back(u, 1);
auto dist = bfs01(0, G);

実装上の補足

edge<T> は dijkstra.cpp と同じ形を使う。 重み 0 の遷移は deque の前、重み 1 の遷移は後ろへ積む。

Verified with

• test/aoj2945_bfs01.test.cpp

Code

template <typename T>
struct edge {
    int from, to; T cost;
    edge(int to, T cost) : from(-1), to(to), cost(cost) {}
    edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
};

template <typename T>
vector<T> bfs01(int s, vector<vector<edge<T>>> &G) {
    int n = G.size();
    vector<T> d(n, INF<T>);
    deque<int> q;
    d[s] = 0;
    q.push_front(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop_front();
        for (auto &&e : G[v]) {
            T nd = d[v] + e.cost;
            if (d[e.to] <= nd) continue;
            d[e.to] = nd;
            if (e.cost == T(0)) {
                q.push_front(e.to);
            } else {
                assert(e.cost == T(1));
                q.push_back(e.to);
            }
        }
    }
    return d;
}

/**
 * @brief 01-BFS
 */

#line 1 "graph/bfs01.cpp"
template <typename T>
struct edge {
    int from, to; T cost;
    edge(int to, T cost) : from(-1), to(to), cost(cost) {}
    edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
};

template <typename T>
vector<T> bfs01(int s, vector<vector<edge<T>>> &G) {
    int n = G.size();
    vector<T> d(n, INF<T>);
    deque<int> q;
    d[s] = 0;
    q.push_front(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop_front();
        for (auto &&e : G[v]) {
            T nd = d[v] + e.cost;
            if (d[e.to] <= nd) continue;
            d[e.to] = nd;
            if (e.cost == T(0)) {
                q.push_front(e.to);
            } else {
                assert(e.cost == T(1));
                q.push_back(e.to);
            }
        }
    }
    return d;
}

/**
 * @brief 01-BFS
 */

Back to top page