algorithm - あらゆる種類の木の直径を計算しますか?

Question

(グラフの理論上の) 無向で、すべてのエッジが重み 1 のツリーの直径を線形時間で計算するアルゴリズムを設計するにはどうすればよいですか? 木の直径は、2 つの頂点間の最長パスの長さによって決まります。

この問題にアプローチする方法について何か考えはありますか?

Answer 1

v1 をツリーの任意の頂点とします。

v1 から深さ優先検索を実行して、v1 から他のすべての頂点の距離を取得し、距離が最大の頂点として v2 を選択します。

v2 から深さ優先検索を実行して、v2 から他のすべての頂点の距離を取得し、距離が最大の頂点として v3 を選択します。

D(v2, v3) は木の直径です。DFS はツリーに対して線形であるため、複雑さは O(|V|) です。