BFS（幅優先探索：Breadth-First search）でグラフのある頂点から各頂点への最短距離を求めることができます。そのコードを整理しました。
定番コードの紹介
グラフ $G$ の表現と入力
$n$ 頂点、$m$ 辺の重み無しグラフ $G$ の表現と入力についてのコードを紹介します。辺は、端の頂点を指定することを仮定します。
- グラフの頂点は、1 から $n$ までとしています（0 から $n-1$ までとする流儀もあります）。このため、グラフの配列を1個余分に確保しています（3行目）。
- 有向グラフの場合は頂点の登録が1行、無向グラフの場合はコメントを外して2行登録します（7－9行目）。
int n, m;
cin >> n >> m;
vector<vector<int>> G(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
// 無向グラフの場合、次の行を有効にする。
// G[v].push_back(u);
}BFSにより最短距離を求める。
キューを使って、ある頂点から各頂点への最短距離を求めます。最短距離は配列 dist に格納します。キューが空になってループを抜けても dist の値が -1 の場合は、たどりつけないことを意味します。
- 配列
distの要素数は、$G$ の表現に合わせて $n+1$ 個確保しています。初期値は、十分に大きな値にする場合と -1 にする場合がありますが、このコードでは、-1 としました。- 初期値を -1 にする場合は、なにかの最小値を求めるときに -1 が干渉する場合があります。
- 初期値を十分大きな値（
INF）にする場合は、INFの定義が必要となります。
- 起点となる頂点は1としました（3、4行目）。
- キューを使って、起点となる頂点から距離が短い順に配列
distを更新します（5ー14行目）。
vector<int> dist(n + 1, -1);
queue<int> que;
que.push(1);
dist[1] = 0;
while (!que.empty()) {
int now = que.front();
que.pop();
for (auto next_v : G[now]) {
if (dist[next_v] == -1) {
que.push(next_v);
dist[next_v] = dist[now] + 1;
}
}
}紹介した定番コードを使った動作するコードを紹介します。
- $n$ 頂点、$m$ 辺の有向グラフを読み込みます。
- BFSで頂点1から、他の頂点への距離を求めます。
- 最後に頂点1から頂点 $n$ への最短距離を出力します。
// 各頂点への最小距離を求める。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> G(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
// 無向グラフの場合、次の行を有効にする。
// G[v].push_back(u);
}
vector<int> dist(n + 1, -1);
queue<int> que;
que.push(1);
dist[1] = 0;
while (!que.empty()) {
int now = que.front();
que.pop();
for (auto next_v : G[now]) {
if (dist[next_v] == -1) {
que.push(next_v);
dist[next_v] = dist[now] + 1;
}
}
}
cout << dist[n] << endl;
return 0;
}BFSを使う問題
タグ「BFS」で関連する記事が探せます。
自分にとって多くを学べた問題を列挙します。
最後に
定番コードの記事を書くことによって、頭を整理したいと考えています。その第一弾となります。
