グラフ（木）の直径を求めるプログラムを紹介します。
定義と手順
木の最も遠い頂点間の距離を木の直径と定義します。
木の直径は、以下の手順で求めることができます。
- ある頂点 $a$ から、もっとも遠い頂点 $b$ を求める。
- その頂点 $b$ から、もっとも遠い頂点 $c$ を求める。
- 頂点 $b$ と頂点 $c$ の距離が木の直径となる。
ある頂点からもっとも遠い頂点は、BFS（幅優先探索：Breadth-First search）でも、DFS（深さ優先探索：Depth-First Search）でも求めることができます。
アルゴリズムのテスト
AIZU ONLINE JUDGE で出題されている問題でアルゴリズムをテストします。以下が問題のリンク先です。
この問題を、BFS を使って解くプログラムは以下です。手順で記載したように BFS を2回使います。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Edge {
int to;
int weight;
Edge(int t, int w) : to(t), weight(w) { }
};
int main()
{
int n;
cin >> n;
vector<vector<Edge>> G(n);
for (int i = 0; i < n - 1; ++i) {
int s, t, w;
cin >> s >> t >> w;
G[s].push_back(Edge(t, w));
G[t].push_back(Edge(s, w));
}
vector<int> dist(n, -1);
queue<int> que;
que.push(0);
dist[0] = 0;
int max_v = 0;
int max_dist = 0;
while (!que.empty()) {
int now = que.front();
que.pop();
for (auto next_v : G[now]) {
if (dist[next_v.to] == -1) {
que.push(next_v.to);
dist[next_v.to] = dist[now] + next_v.weight;
if (dist[next_v.to] > max_dist) {
max_v = next_v.to;
max_dist = dist[next_v.to];
}
}
}
}
dist.assign(n, -1);
que.push(max_v);
dist[max_v] = 0;
max_dist = 0;
while (!que.empty()) {
int now = que.front();
que.pop();
for (auto next_v : G[now]) {
if (dist[next_v.to] == -1) {
que.push(next_v.to);
dist[next_v.to] = dist[now] + next_v.weight;
max_dist = max(max_dist, dist[next_v.to]);
}
}
}
cout << max_dist << endl;
return 0;
}次に DFS を使って解くプログラムは以下です。
#include <iostream>
#include <vector>
using namespace std;
struct Edge {
int to;
int weight;
Edge(int t, int w) : to(t), weight(w) { }
};
vector<vector<Edge>> G;
vector<int> dist;
int max_v = 0;
int max_dist = 0;
void dfs(int v, int par, int d)
{
dist[v] = d;
if (dist[v] > max_dist) {
max_v = v;
max_dist = dist[v];
}
for (auto next_v : G[v]) {
if (next_v.to != par) {
dfs(next_v.to, v, d + next_v.weight);
}
}
}
int main()
{
int n;
cin >> n;
G.resize(n);
for (int i = 0; i < n - 1; ++i) {
int s, t, w;
cin >> s >> t >> w;
G[s].push_back(Edge(t, w));
G[t].push_back(Edge(s, w));
}
dist.assign(n, -1);
dfs(0, -1, 0);
dist.assign(n, -1);
dfs(max_v, -1, 0);
cout << max_dist << endl;
return 0;
}どちらもACと判定されました。
最後に
この記事を書くことで、木の直径に対する理解が深まりました。
