bfs (simple ver)
(src/graph/simple/bfs.hpp)

• View this file on GitHub
• Last update: 2022-12-06 05:52:08+09:00
• Include: #include "src/graph/simple/bfs.hpp"

概要

コストなしグラフ $G(V, E)$ の単一始点最短経路問題を解きます。

最短経路木の情報が欲しい場合はsrc/graph/BFS.hppを使ってください

機能

std::vector<int> bfs(const std::vector<std::vector<int>>& G, int s, int inf = 2e9)

• G: グラフの隣接リストを表す二次元vector
  • 頂点iから頂点G[i][j]に有向辺が存在するようにする。
  • AtCoderなら、zawa::read_graphで標準入力から対応するGを生成できます。

• s: 始点

• inf: 最短経路テーブルの初期値
  • デフォルトで $2\times 10^9$ ですが、基本自分で指定したほうが良いです。
• 返り値: res[i]には、頂点sから頂点iへ行くために通る最小辺数が入っています。
  • sからiへ到達不可能である場合、infが入ります。
• 計算量: $O(\mid V \mid + \mid E \mid)$

Verified with

• test/ABC291-F.test.cpp
• test/simple-bfs1.test.cpp
• test/simple-bfs2.test.cpp

Code

#pragma once

#include <vector>
#include <queue>

namespace zawa {

std::vector<int> bfs(const std::vector<std::vector<int>>& G, int s, int inf = 2e9) {
    std::vector<int> res(G.size(), inf);
    res[s] = 0;
    std::queue<int> que({ s });
    while (que.size()) {
        int v = que.front();
        que.pop();
        for (auto x : G[v]) {
            if (res[x] > res[v] + 1) {
                res[x] = res[v] + 1;
                que.push(x);
            }
        }
    }
    return res;
}

} // namespace zawa

#line 2 "src/graph/simple/bfs.hpp"

#include <vector>
#include <queue>

namespace zawa {

std::vector<int> bfs(const std::vector<std::vector<int>>& G, int s, int inf = 2e9) {
    std::vector<int> res(G.size(), inf);
    res[s] = 0;
    std::queue<int> que({ s });
    while (que.size()) {
        int v = que.front();
        que.pop();
        for (auto x : G[v]) {
            if (res[x] > res[v] + 1) {
                res[x] = res[v] + 1;
                que.push(x);
            }
        }
    }
    return res;
}

} // namespace zawa

Back to top page