木の直径

概要

重み付きグラフにおいて，2 頂点の距離の最大値を直径と言う．木の直径は線形時間で求められる．最初に適当な頂点 $s$ から最も遠い点 $u$ を求め，次に $u$ から最も遠い点 $v$ を求めると，$u$ と $v$ が距離最大となる．このアルゴリズムを double sweep と (俗に？) 言う．

使い方

辞書順で最小の組が (u, v) で距離が w のとき，辺の構造体 {u, v, w} を返す．

計算量

$O(V)$

実装

Edge double_sweep(const Graph &g, int s = 0) {
    static const Weight INF = std::numeric_limits<Weight>::max() / 8;
    static const auto bfs = [](const Graph &g, int s, std::queue<int> &q, std::vector<int> &dist) {
        while (q.size()) q.pop();
        q.push(s);
        int n = g.size();
        dist.assign(n, INF);
        dist[s] = 0;
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (auto &e : g[u]) {
                int v = e.dst;
                if (dist[v] == INF) {
                    dist[v] = dist[u] + e.weight;
                    q.push(v);
                }
            }
        }
        return dist;
    };
    std::vector<Weight> dist;
    std::queue<int> q;
    bfs(g, s, q, dist);
    int n = g.size(), u = -1, v = -1;
    for (int i = 0; i < n; i++)
        if (dist[i] != INF && (u == -1 || dist[i] > dist[u])) u = i;
    bfs(g, u, q, dist);
    for (int i = 0; i < n; i++)
        if (dist[i] != INF && (v == -1 || dist[i] > dist[v])) v = i;
    Weight d = dist[v];
    if (u > v) std::swap(u, v);
    return Edge(u, v, d);
}

検証

GRL5A http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2189317