BFS
(graph/shortest-path/bfs.hpp)

• View this file on GitHub
• Last update: 2023-11-04 18:06:00+09:00
• Include: #include "graph/shortest-path/bfs.hpp"

Depends on

• グラフ構造体 (graph/graph_template.hpp)

Code

#pragma once

#include <functional>
#include <limits>
#include <queue>
#include <utility>

#include "../graph_template.hpp"

template <typename Cost = int>
std::pair<std::vector<Cost>, std::vector<int>>
bfs(const Graph<Cost> &G, int start, Cost iv = 0,
    Cost inf = std::numeric_limits<Cost>::max()) {
    using Data = std::pair<Cost, int>;
    int N = (int)G.size();
    std::vector<Cost> dist(N, inf);
    std::vector<int> prev(N, -1);

    dist[start] = iv;
    std::queue<int> que;
    que.emplace(start);
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        for(const auto &e : G[u]) {
            if(dist[e.to] > dist[u] + 1) {
                dist[e.to] = dist[u] + 1;
                prev[e.to] = u;
                que.emplace(e.to);
            }
        }
    }

    return std::make_pair(dist, prev);
}

#line 2 "graph/shortest-path/bfs.hpp"

#include <functional>
#include <limits>
#include <queue>
#include <utility>

#line 2 "graph/graph_template.hpp"

#include <cassert>
#include <vector>

template <typename Cost = int> struct Edge {
    int from, to;
    Cost cost;
    int id;
    Edge() = default;
    explicit Edge(int from, int to, Cost cost = 1, int id = -1)
        : from(from), to(to), cost(cost), id(id) {}
    operator int() const { return to; }
};

template <typename Cost = int> class Graph {
  public:
    Graph() = default;
    explicit Graph(int N) : N(N), M(0), G(N) {}

    inline void add_directed_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M++);
    }

    inline void add_undirected_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M);
        G[to].emplace_back(to, from, cost, M++);
    }

    inline size_t size() const { return G.size(); }
    inline std::vector<Edge<Cost>> &operator[](const int &i) { return G[i]; }
    inline const std::vector<Edge<Cost>> &operator[](const int &i) const {
        return G[i];
    }

  protected:
    int N, M;
    std::vector<std::vector<Edge<Cost>>> G;
};

template <class Cost = int> using Edges = std::vector<Edge<Cost>>;
#line 9 "graph/shortest-path/bfs.hpp"

template <typename Cost = int>
std::pair<std::vector<Cost>, std::vector<int>>
bfs(const Graph<Cost> &G, int start, Cost iv = 0,
    Cost inf = std::numeric_limits<Cost>::max()) {
    using Data = std::pair<Cost, int>;
    int N = (int)G.size();
    std::vector<Cost> dist(N, inf);
    std::vector<int> prev(N, -1);

    dist[start] = iv;
    std::queue<int> que;
    que.emplace(start);
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        for(const auto &e : G[u]) {
            if(dist[e.to] > dist[u] + 1) {
                dist[e.to] = dist[u] + 1;
                prev[e.to] = u;
                que.emplace(e.to);
            }
        }
    }

    return std::make_pair(dist, prev);
}

Back to top page