木の直径
概要
木の存在するノード間の最大距離を 木の直径 を呼ぶ。
重みの有無に関わらず、木の最遠頂点間距離が直径となる。
木の直径は下記の事実を利用して求められる。(証明は参考リンクを参照)
「どの頂点から探索しても、最も遠くにある頂点 x は木の直径の端点になる」
アルゴリズム
- 任意の頂点 s を選ぶ
- s から DFS/BFS によって、最も遠くにある頂点 u を探索する (1 つ目の直径の端点)
- u から DFS/BFS によって、最も遠くにある頂点 v を探索する (2 つ目の直径の端点)
- u と v を結ぶパスが直径となる
重みの有/無は関係しない。同様のアルゴリズムで探索可能
\(M\) を辺数、\(N\) を頂点数としたとき、計算量は \(O(M+N)\)