樹中最長路徑的線性時間算法

Question

我被賦予了一個讓我難倒的任務的問題。我可能只是在想太多的問題......接下來的問題。

給出線性時間算法以確定非循環無向圖（即樹）中最長的未加權路徑。

我的第一個意圖是去一個DFS。但是看起來DFS只會給我從節點開始到另一個頂點的最長路徑;然而，問題是要求樹中最長的路徑......而不是從節點I開始的最長路徑。有人能讓我挺身而出嗎？

謝謝。

Answer 1

一種這樣的方法是挑選任何節點A，並以線性時間計算到所有其他節點的距離。假設B距離A最遠。在步驟2中，找到離B最遠的節點。

設d（P，Q）表示從P到Q的距離。注意，如果E是A的最低公共祖先， B，C，則d（A，B）= d（A，E）+ d（E，B） 並且還注意到d（​​E，B）≥d（E，C）。

編輯1：算法或方法 - 找到B距離任何A最遠;找到距離B最遠的C;聲稱d（B，C）在圖中的所有頂點對中都是最大的 - 似乎是合理的，但上述內容並不能證明它。一方面，它不一定是d（E，B）≥d（E，C），另一方面，單獨不足以建立d（B，C）≥d（F ，G）其中F，G是樹中的任何節點。 ...