Tree Diameter Algorithm

コードについての説明

木の直径を求めるアルゴリズム.
木の直径とは木上の異なる $2$ 点の組でその間の距離が最大となるようなものを $u, v$ としたとき $u, v$ を端点とするパス上の頂点の列のことをいう. 一般に木の直径は一意に定まらないことに注意する.
求める方法はある点 $u$ から一番遠い点を探索し $v$ であったとする. その $v$ から一番遠い点を探索し $w$ であったとするとこのとき $v, w$ が木の直径の端点となっていることがいえる.
(証明)
以上の事実が自明でないので証明を考えます. 木上のパスで $(u, v)$ より長い $(x, y)$ があったとします. このとき $u$ を根とする木において $v$ と $x$ の LCA(最小共通祖先) となる頂点を $a, v$ と $y$ の LCA となる頂点を $b$ とします($a = b$ の場合も考慮しています). このとき $a, b$ ともに $v$ の祖先だが, $v, a$ 間の距離が $v, b$ 間の距離より長くないとして一般性を失わない. また頂点 $v$ と $w$ の LCA となる頂点を $c$ とする. また以後頂点 $i, j$ 間の単純パスを $P_{ij}$ と表すことにする(木なので $i, j$ に対して一意に定まる).
(i) $v, a$ 間の距離が $v, c$ 間の距離より長くないとき
このとき, $P_{xy} = P_{xa} + P_{ay}$, $P_{vw} = P_{va} + P_{aw}$ であり, 頂点 $v$ が頂点 $u$ から一番遠い点であるという事実から $|P_{xa}| \le |P_{va}|$, 頂点 $w$ が頂点 $v$ から一番遠い点であるという事実から $|P_{ay}| \le |P_{aw}|$ が成り立つ. よって $|P_{xy}| = |P_{xa}| + |P_{ay}| \le |P_{va}| + |P_{aw}| = |P_{vw}|$ となり仮定に矛盾.
(ii) $v, a$ 間の距離が $v, c$ 間の距離より長いとき
$P_{xy} = P_{xa} + P_{ab} + P_{by}$, $P_{vw} = P_{vc} + P_{cw}$ であり, 頂点 $v$ が頂点 $u$ から一番遠い点であるという事実から $|P_{xa}| \le |P_{vc}| + |P_{ca}|$, 頂点 $w$ が頂点 $v$ から一番遠い点であるという事実から $|P_{ca}| + |P_{ab}| + |P_{by}| \le |P_{cw}|$ が成り立つ. よって $|P_{xy}| = |P_{xa}| + |P_{ab}| + |P_{by}| \le |P_{vc}| + |P_{ca}| + |P_{ab}| + |P_{by}| \le |P_{vc}| + |P_{cw}| = |P_{vw}|$ となり仮定に矛盾.
よって示せた.
ちなみにこの考え方を一般のグラフに対してそのまま用いることでグラフの直径の $2$ 近似を得ることもできる.

(関数)
solve(): 木の直径を計算し, $diameter$ に格納する

時間計算量: $\O (n)$

コード

class TreeDiameter {
private:
    int V;
    vector<vector<int> > G;
    void dfs(int u,int p,int d,int& far,int& mx){
        if(mx < d){
            far = u;
            mx = d;
        }
        for(int v : G[u]){
            if(v != p){
                dfs(v,u,d+1,far,mx);
            }
        }
    }
    bool redfs(int u,int p,const int t){
        if(u == t){
            return true;
        }
        for(int v : G[u]){
            if(v != p){
                diameter.push_back(v);
                if(redfs(v,u,t)){
                    return true;
                }else{
                    diameter.pop_back();
                }
            }
        }
        return false;
    }

public:
    vector<int> diameter;
    TreeDiameter(int node_size) : V(node_size), G(V){}
    void add_edge(int u,int v){
        G[u].push_back(v),G[v].push_back(u);
    }
    void solve(){
        int s,t,mx;
        mx = -1;
        dfs(0,-1,0,s,mx);
        mx = -1;
        dfs(s,-1,0,t,mx);
        diameter.push_back(s);
        redfs(s,-1,t);
    }
};

verify 用の問題

AOJ : Crossing Tree 提出コード