木の直径
木の直径とは？
木の直径とは、重みなし、または非負の重み付き木における最も遠い頂点同士の距離のことである。
難しい言い方で最遠頂点間の距離という。
求め方
木から任意の頂点を一つ選ぶ。そしてその頂点から全頂点への距離を求める。
そうすることで、最初に選んだ頂点から最も遠い頂点$ uがわかる。
その頂点を開始点にしてもう一度全頂点への距離を求める。
そこで最も距離が遠い頂点$ vを選ぶと、必ず$ u, vが直径を構成する頂点の一つになる。
なお、$ u, vの候補がいくつあったとしても、それら全てについて直径を構成する頂点対と呼べる。
計算量は重みなし木なら$ Ο(N)となり、非負の重み付き木なら$ Ο(N \log N)となる。
このアルゴリズムで求められることの証明は背理法などを用いれば良いが、複雑なので割愛する。
疑問点
ベルマンフォードとか通せば重みの正負を問わない気がするが、どうなんだろうか