BFS (幅優先探索)
(src/graph/BFS.hpp)

• View this file on GitHub
• Last update: 2022-11-13 19:29:23+09:00
• Include: #include "src/graph/BFS.hpp"

概要

zawa::BFS(std::size_t n)

重み無しグラフにおいて幅優先探索を行い、単一始点最短経路を求めます。

機能

• コンストラクタ: 頂点数を引数に取ります。負でない整数を入れてください

$0\ \le\ N\ \le\ 2^{31} - 1$

• int add_edge(int from, int to): fromからtoへの有向辺を追加します。追加された辺の番号を返します(0-indexed)。

$0\ \le\ \text{from},\ \text{to}\ \le\ N - 1$

• std::pair<int, int> get_edge(int id): id番目に追加された辺の情報を返します(境界値チェックが無いことに注意)。{ from, to }です。
• void build(int s): 頂点sからの単一始点最短経路を求めます。
• int inf(): コストの初期値を返します。（すなわち、頂点sから到達できな頂点の距離にinf()が記録されています。
• int get_dist(int v): 頂点sから頂点vへの最短距離を返します。
• int get_prev(int v): 頂点sを根としたグラフの最短経路木を生成した時、頂点vの親を返します。
• int get_route(int v): 頂点sを根としたグラフの最短経路木を生成した時、頂点vの親とv自身をつないでいる辺の番号を返します。

計算量

buildは $O(N + M)$ ( $M$ は辺数)

Verified with

• test/BFS.test.cpp

Code

#pragma once

#include <queue>
#include <vector>
#include <limits>
#include <utility>

namespace zawa {

class BFS {
public:

    BFS(std::size_t n)
        : G(n)
        , dist(n, _inf)
        , prevs(n, -1)
        , route(n, -1) {}

    int add_edge(int from, int to) {
        int res = (int)edges.size();
        edges.push_back({ from, to });
        G[from].emplace_back(res);
        return res;
    }

    std::pair<int, int> get_edge(int id) {
        return edges[id];
    }

    void build(int s) {
        dist[s] = 0;
        std::queue<int> que({ s });
        while (que.size()) {
            int v = que.front();
            que.pop();
            for (auto x : G[v]) {
                auto [_, t] = edges[x];
                if (dist[t] > dist[v] + 1) {
                    dist[t] = dist[v] + 1;
                    prevs[t] = v;
                    route[t] = x;
                    que.emplace(t);
                }
            }
        }
    }

    int inf() {
        return _inf;
    }

    int get_dist(int v) {
        return dist[v];
    }

    int get_prev(int v) {
        return prevs[v];
    }

    int get_route(int v) {
        return route[v];
    }

private:
    static constexpr int _inf = std::numeric_limits<int>::max();
    std::vector<std::pair<int, int>> edges;
    std::vector<std::vector<int>> G;
    std::vector<int> dist;
    std::vector<int> prevs;
    std::vector<int> route;
};

}// namespace zawa

#line 2 "src/graph/BFS.hpp"

#include <queue>
#include <vector>
#include <limits>
#include <utility>

namespace zawa {

class BFS {
public:

    BFS(std::size_t n)
        : G(n)
        , dist(n, _inf)
        , prevs(n, -1)
        , route(n, -1) {}

    int add_edge(int from, int to) {
        int res = (int)edges.size();
        edges.push_back({ from, to });
        G[from].emplace_back(res);
        return res;
    }

    std::pair<int, int> get_edge(int id) {
        return edges[id];
    }

    void build(int s) {
        dist[s] = 0;
        std::queue<int> que({ s });
        while (que.size()) {
            int v = que.front();
            que.pop();
            for (auto x : G[v]) {
                auto [_, t] = edges[x];
                if (dist[t] > dist[v] + 1) {
                    dist[t] = dist[v] + 1;
                    prevs[t] = v;
                    route[t] = x;
                    que.emplace(t);
                }
            }
        }
    }

    int inf() {
        return _inf;
    }

    int get_dist(int v) {
        return dist[v];
    }

    int get_prev(int v) {
        return prevs[v];
    }

    int get_route(int v) {
        return route[v];
    }

private:
    static constexpr int _inf = std::numeric_limits<int>::max();
    std::vector<std::pair<int, int>> edges;
    std::vector<std::vector<int>> G;
    std::vector<int> dist;
    std::vector<int> prevs;
    std::vector<int> route;
};

}// namespace zawa

Back to top page