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としました（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」で関連する記事が探せます。
自分にとって学ぶことができた問題を列挙します。
最後に
定番コードの記事を書くことによって、頭を整理したいと考えています。その第一弾となります。
