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

• View this file on GitHub
• Last update: 2022-11-14 21:43:27+09:00
• Include: #include "src/graph/01BFS.hpp"

概要

zawa::Zero_One_BFS(std::size_t n)

辺の重みが0又は1のグラフにおいて幅優先探索を行い、単一始点最短経路を求めます。

機能

• コンストラクタ: 頂点数を引数に取ります。負でない整数を入れてください $0\ \le\ N\ \le\ 2^{31} - 1$
• int add_zero_edge(int from, int to): fromからtoへ重み0の有向辺を追加します。追加された辺の番号を返します(0-indexed)。
• int add_one_edge(int from, int to): fromからtoへ重み1の有向辺を追加します。追加された辺の番号を返します(0-indexed)。

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

• edge構造体: from、toがint型、costがbool型

• edge get_edge(int id): id番目に追加された辺の情報を返します(境界値チェックが無いことに注意)。
• void build(int s): 頂点sからの単一始点最短経路を求めます。それ以前のbuildの情報が失われることに注意してください
• 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/01BFS.test.cpp

Code

#pragma once

#include <vector>
#include <deque>
#include <limits>
#include <utility>
#include <algorithm>

namespace zawa {

class Zero_One_BFS {
public:

    struct edge {
        int from, to;
        bool cost;
    };

    Zero_One_BFS(std::size_t n)
        : G(n, std::vector(0, 0))
        , edges(0, edge())
        , dist(n, _inf)
        , prevs(n, -1)
        , route(n, -1) {}

    int add_zero_edge(int from, int to) {
        return add_edge(from, to, false);
    }

    int add_one_edge(int from, int to) {
        return add_edge(from, to, true);
    }

    inline edge get_edge(int id) {
        return edges[id];
    }

    void build(int s) {
        std::fill(dist.begin(), dist.end(), _inf);
        std::fill(prevs.begin(), prevs.end(), -1);
        std::fill(route.begin(), route.end(), -1);
        dist[s] = 0;
        std::deque<int> deq({ s });
        while (deq.size()) {
            int v = deq.front();
            deq.pop_front();
            for (auto x : G[v]) {
                auto [_, t, cost] = edges[x];
                if (dist[t] > dist[v] + (int)cost) {
                    dist[t] = dist[v] + (int)cost;
                    prevs[t] = v;
                    route[t] = x;
                    if (cost) {
                        deq.push_back(t);
                    }
                    else {
                        deq.push_front(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::vector<int>> G;
    std::vector<edge> edges;
    std::vector<int> dist;
    std::vector<int> prevs;
    std::vector<int> route;
    
    int add_edge(int from, int to, bool cost) {
        int res = (int)edges.size();
        edges.push_back({ from, to, cost });
        G[from].push_back(res);
        return res;
    }
};

}// namespace zawa

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

#include <vector>
#include <deque>
#include <limits>
#include <utility>
#include <algorithm>

namespace zawa {

class Zero_One_BFS {
public:

    struct edge {
        int from, to;
        bool cost;
    };

    Zero_One_BFS(std::size_t n)
        : G(n, std::vector(0, 0))
        , edges(0, edge())
        , dist(n, _inf)
        , prevs(n, -1)
        , route(n, -1) {}

    int add_zero_edge(int from, int to) {
        return add_edge(from, to, false);
    }

    int add_one_edge(int from, int to) {
        return add_edge(from, to, true);
    }

    inline edge get_edge(int id) {
        return edges[id];
    }

    void build(int s) {
        std::fill(dist.begin(), dist.end(), _inf);
        std::fill(prevs.begin(), prevs.end(), -1);
        std::fill(route.begin(), route.end(), -1);
        dist[s] = 0;
        std::deque<int> deq({ s });
        while (deq.size()) {
            int v = deq.front();
            deq.pop_front();
            for (auto x : G[v]) {
                auto [_, t, cost] = edges[x];
                if (dist[t] > dist[v] + (int)cost) {
                    dist[t] = dist[v] + (int)cost;
                    prevs[t] = v;
                    route[t] = x;
                    if (cost) {
                        deq.push_back(t);
                    }
                    else {
                        deq.push_front(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::vector<int>> G;
    std::vector<edge> edges;
    std::vector<int> dist;
    std::vector<int> prevs;
    std::vector<int> route;
    
    int add_edge(int from, int to, bool cost) {
        int res = (int)edges.size();
        edges.push_back({ from, to, cost });
        G[from].push_back(res);
        return res;
    }
};

}// namespace zawa

Back to top page