木の直径

直径とは

直径とは、グラフ内の二点間の距離における最長のものの値であり、式で表すと以下のようになります。

     \begin{equation*} D := \underset{u,v \in V}{{\rm max}} \: {\rm dist}(u,v) \end{equation*}

Double sweep

グラフ木の場合、以下の方法で木の直径を求めることができます。

  1. 適当な点からDFSし、最も遠い点uを見つける。
  2. 点uからDFSをし、最も遠い点vを見つける。
  3. dist(u,v)が木の直径である。

一般のグラフの直径

一般のグラフに対してはDouble sweepを用いることはできません。

競プロではワーシャルフロイドで全頂点の距離を計算し、最長距離を求めるので十分でしょう。

Dijkstraでdouble sweep、ダメ、絶対。

参考