選擇一棵樹的根，使樹的高度最小

在我試圖解決的一個算法問題 - 我處於一種情況下，我得到一棵樹，我需要選擇一個節點作爲樹高爲最低的根。選擇一棵樹的根，使樹的高度最小

有200,000個節點和150,000條邊。由於時間的限制，我需要一個比O(n^2)更好的算法。

我可以使用什麼算法？

2015-12-16 Donotalo

因此，你在找什麼被稱爲樹的中心，這已被討論[這裏]（http://stackoverflow.com/questions/4020122/finding-center-of-the-tree） –

@ PhamTrung：很好。謝謝。我不知道樹的中心這個詞。你爲什麼不把它作爲答案發布，以便我可以選擇它作爲最佳答案？ – Donotalo

選擇任何節點並假定它是根。運行DFS以查找距離最遠的葉子的距離。這將基本上計算樹的高度，如果你選擇第一個節點作爲根。

接下來，通過查找樹的中心找到正確的根。要做到這一點，你看當前根的孩子，並選擇最大的高度（距離最遠的葉子最大的距離）。如果將根移動到該子節點，則新節點的高度將在該節點中已有的值與當前根節點的其他樹葉的下一個最大值之間變化。你應用這個，移動根，直到你不能再降低高度。這是樹的一箇中心（可能更多）以及您正在尋找的解決方案。

初始DFS是O（N）。在優化距離時，無法訪問節點兩次，每個步驟都是O（1）攤銷，因此總體上它是O（N）。 O（1）分期償還，因爲一個節點可能有很多孩子，但你只考慮過一次（在你移動後你不能回去，所以你不能再次檢查它們），所以即使你檢查整棵樹，你會檢查O（N）個孩子。

來源

2015-12-16 10:26:02 Sorin

我認爲樹的中心應該是樹的根所需的節點，因爲如果根是樹的中心，從根到任何節點的最大距離是最小的。

來源

2015-12-16 08:59:39 Daga

選擇一棵樹的根，使樹的高度最小

回答

相關問題