木の直径

説明

非負の重みを持つ無向の木が与えられたとき，木の直径，すなわち最遠頂点間距離を求める．

アルゴリズム自体はシンプルである．まず適当な頂点 s から探索を行い，最も遠い頂点 u を求める．次に u から探索を行い，最も遠い頂点 v を求める．このとき (u, v) は最遠頂点対である．

実行時間が O( E ) となることは明らかである．探索に深さ優先探索を用いれば，定数も（行数も）小さくすむ．そこで以下アルゴリズムの正当性を証明する．

アルゴリズムの正当性のためには，木の最遠頂点対を x, y としたとき，x または y として s からの最遠頂点 u を選んでもかまわないことを証明すれば十分である．s からの最遠頂点を u とし，s からの経路で，u と x が分かれる点を t と置く．y の位置について，次のように場合わけを行う．

• y が s-t 間にある場合：y を s に取り直しても距離は減らないので d(s,u) ≧ d(s,x) ≧ d(y,x) より x = u に取って十分．
• y が t-x 間にある場合：y を s に取り直しても距離は減らないので上と同じ．
• y が t-u 間にある場合：u が s からの最遠頂点なので d(u,x) = d(u,t) + d(t,x) ≧ d(y,t) + d(t,x) = d(y,x) となり，y = u に取って十分．
• それ以外：これは y が s を挟んで t と逆側にある場合だが，u の最遠性から d(u,y) = d(u,s) + d(s,y) ≧ d(x,s) + d(s,y) = d(x,y) となり，x = u に取って十分．

以上で証明された．

計算量

O(E)

使い方

const Graph &g

無向きの木．

戻り値

最遠頂点対間の距離．

ソースコード

typedef pair<Weight, int> Result;
Result visit(int p, int v, const Graph &g) {
  Result r(0, v);
  FOR(e, g[v]) if (e->dst != p) {
    Result t = visit(v, e->dst, g);
    t.first += e->weight;
    if (r.first < t.first) r = t;
  }
  return r;
}
Weight diameter(const Graph &g) {
  Result r = visit(-1, 0, g);
  Result t = visit(-1, r.second, g);
  return t.first; // (r.second, t.second) is farthest pair
}

Verified

• UVA のどこか