木の高さ

説明

非負の重みを持つ無向の木が与えられたとき，各頂点について，それを根にしたときの高さ（もっとも遠い葉までの距離）を線型時間 O( E ) で求める．

アルゴリズムは動的計画法に基づく．頂点 s から辺 e = (s,t) を使って行ける最遠頂点までの距離を f(s,e) とすると，f(s,e) = w(e) + max { f(t,e') | e' \ne e } となる（ e' \ne e は無向グラフなので逆辺があることを考慮している）．これをメモ化すれば，すべての辺が一度ずつ確定するので O( E ) で終了する．

なお，木の直径（高さの最大値）は，これとは別のアルゴリズムによって（同じく線型だが）より高速に求めることができる．

計算量

O(E)

使い方

const Graph &g

無向きの木．

戻り値

頂点 u について ht[u] は u の高さ．

ソースコード

Weight visit(const Graph &g, Graph& T, int i, int j) {
  if (T[i][j].weight >= 0) return T[i][j].weight;
  T[i][j].weight = g[i][j].weight;
  int u = T[i][j].dst;
  REP(k, T[u].size()) {
    if (T[u][k].dst == i) continue;
    T[i][j].weight = max(T[i][j].weight, visit(g,T,u,k)+g[i][j].weight);
  }
  return T[i][j].weight;
}
vector<Weight> height(const Graph& g) {
  const int n = g.size();
  Graph T(g); // memoise on tree
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < T[i].size(); ++j)
      T[i][j].weight = -1;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < T[i].size(); ++j)
      if (T[i][j].weight < 0)
        T[i][j].weight = visit(g, T, i, j);

  vector<Weight> ht(n); // gather results
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < T[i].size(); ++j)
      ht[i] = max(ht[i], T[i][j].weight);
  return ht;
}

Verified

• UVA のどこか