Spaghetti Source logo

木の直径

説明

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

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

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

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

以上で証明された.

計算量

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

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.11.14 20:36:16.