0or1幅優先探索. 01BFS
(ugilib/graph/bfs.hpp)

• View this file on GitHub
• Last update: 2024-04-03 22:46:30+09:00
• Include: #include "ugilib/graph/bfs.hpp"

Depends on

• ugilib/base/constants.hpp
• ugilib/base/definitions.hpp

Verified with

• tests/graph/bfs.test.cpp

Code

#pragma once
#include <bits/stdc++.h>
#include "ugilib/base/constants.hpp"

using namespace std;

namespace ugilib {
    /**
     * @brief 0or1幅優先探索. 01BFS
     * @param n グラフの頂点数
     * @param start 始点
     * @param graph グラフ. vector<pair<int, weight_type>> で隣接頂点とコストを表す. コストは0 or 1
     * @param weight_inf 無限大の値. パスが存在しない場合のコスト
     * @return 始点から各頂点までの最短距離
     * @note O(E+V)
     * @todo 01BFS問題でのテストを書く
    */
    template <typename weight_type>
    vector<weight_type> bfs01(int n, int start, const vector<vector<pair<int, weight_type>>> &graph, weight_type weight_inf = ugilib::constants::INF<weight_type>) {
        vector<weight_type> costs(n, weight_inf);
        costs[start] = 0;

        deque<int> next_nodes;
        next_nodes.push_back(start);

        while (!next_nodes.empty()) {
            auto node = next_nodes.front(); next_nodes.pop_front();
            auto cost = costs[node];

            for (const auto [next_node, next_cost] : graph[node]) {
                auto new_cost = cost + next_cost;
                if (new_cost < costs[next_node]) {
                    costs[next_node] = new_cost;
                    // 0or1幅優先探索の場合, コストが0の場合は前から入れ, 1の場合は後ろに入れる
                    if (next_cost == 0) next_nodes.push_front(next_node);
                    else next_nodes.push_back(next_node);
                }
            }
        }

        return costs;
    }
}  // namespace ugilib

#line 2 "ugilib/graph/bfs.hpp"
#include <bits/stdc++.h>
#line 2 "ugilib/base/definitions.hpp"

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i, n) for(size_t i = 0; i < n; i++)  // rep macro
#define all(v) begin(v), end(v)  // all iterator
#line 3 "ugilib/base/constants.hpp"

namespace ugilib::constants {
    template<typename T>
    inline constexpr T INF = std::numeric_limits<T>::max() / 2;
} // namespace ugilib::constants

const ll INF = ugilib::constants::INF<ll>;
#line 4 "ugilib/graph/bfs.hpp"

using namespace std;

namespace ugilib {
    /**
     * @brief 0or1幅優先探索. 01BFS
     * @param n グラフの頂点数
     * @param start 始点
     * @param graph グラフ. vector<pair<int, weight_type>> で隣接頂点とコストを表す. コストは0 or 1
     * @param weight_inf 無限大の値. パスが存在しない場合のコスト
     * @return 始点から各頂点までの最短距離
     * @note O(E+V)
     * @todo 01BFS問題でのテストを書く
    */
    template <typename weight_type>
    vector<weight_type> bfs01(int n, int start, const vector<vector<pair<int, weight_type>>> &graph, weight_type weight_inf = ugilib::constants::INF<weight_type>) {
        vector<weight_type> costs(n, weight_inf);
        costs[start] = 0;

        deque<int> next_nodes;
        next_nodes.push_back(start);

        while (!next_nodes.empty()) {
            auto node = next_nodes.front(); next_nodes.pop_front();
            auto cost = costs[node];

            for (const auto [next_node, next_cost] : graph[node]) {
                auto new_cost = cost + next_cost;
                if (new_cost < costs[next_node]) {
                    costs[next_node] = new_cost;
                    // 0or1幅優先探索の場合, コストが0の場合は前から入れ, 1の場合は後ろに入れる
                    if (next_cost == 0) next_nodes.push_front(next_node);
                    else next_nodes.push_back(next_node);
                }
            }
        }

        return costs;
    }
}  // namespace ugilib

Back to top page