[latexpage]
Contents
直径とは
直径とは、グラフ内の二点間の距離における最長のものの値であり、式で表すと以下のようになります。
Double sweep
グラフ木の場合、以下の方法で木の直径を求めることができます。
- 適当な点からDFSし、最も遠い点uを見つける。
- 点uからDFSをし、最も遠い点vを見つける。
- dist(u,v)が木の直径である。
一般のグラフの直径
一般のグラフに対してはDouble sweepを用いることはできません。
競プロではワーシャルフロイドで全頂点の距離を計算し、最長距離を求めるので十分でしょう。
Dijkstraでdouble sweep、ダメ、絶対。
参考
- グラフの直径の計算量について (Qiita)