計算任何一種樹的直徑？

Question

如何設計一個算法，以線性時間計算（圖理論）無向，全邊有權重1樹的直徑？樹的直徑由兩個頂點之間最長路徑的長度給出。

任何想法如何解決這個問題？

Answer 1

設v1是樹中的任何頂點。

從v1開始進行深度優先搜索，從v1中獲取所有其他頂點的距離，選擇v2作爲距離最遠的頂點。

從v2開始進行深度優先搜索，從v2中獲取所有其他頂點的距離，選擇v3作爲距離最高的頂點。

D（v2，v3）是樹的直徑。複雜度爲O（| V |），因爲DFS對於樹是線性的。