將樹拆分成相等部分

我正在尋找一種算法，通過從中刪除一條邊來拆分具有N個節點（其中每個節點的最大度數爲3）的樹，以便作爲結果出現的兩棵樹儘可能接近N/2。我如何找到「最集中」的邊緣？將樹拆分成相等部分

該樹作爲來自算法前一階段的輸入，並作爲圖形輸入 - 因此它不平衡，也不清楚哪個節點是根。

我的想法是找到樹中最長的路徑，然後選擇最長路徑中間的邊。它工作嗎？

理想情況下，我正在尋找一種解決方案，可以確保兩棵樹都不超過2N/3個節點。

感謝您的回答。

來源

2011-11-24 anonymous

如果你沒有關於樹的佈局平衡的數據，你可以從一棵退化的樹開始（比如左臂100個，右臂50個），然後以50/100分割結束同一條船。 –

是的，但是選取長度爲150的最長路徑，並將中間邊緣（路徑上的第75或第76）分成相等的部分。問題是這樣一個最優邊緣是否會一直存在（我不這麼認爲）。 – anonymous

退化樹基本上是一個鏈表。例如具有兩個孩子的唯一節點是根節點。所以你會有兩條從根節點通過樹的路徑。左邊有100個線性節點，右邊是50個，右邊是50個。分割最長的路徑（100個節點分支）將100分成50/50，再加上右邊分支的剩餘部分，所以你已經將樹從100/50至50/100。 –

我不相信你的初始算法適用於我在評論中提到的原因。不過，我認爲你可以使用修改後的DFS在O（n）時間和空間中解決這個問題。

開始步行圖來統計有多少個節點;稱這個n。現在，選擇一個任意節點並將其樹根。我們現在將遞歸探索從根開始的樹，並將爲每個子樹計算每個子樹中有多少個節點。這可以用一個簡單的遞歸來完成：

如果當前節點爲null，則返回0。
否則：
- 對於每一個孩子，計算節點的數量在該子根的子樹。
- 返回1 +在所有子節點的總數子樹

在這一點上，我們知道每個邊有什麼分裂，我們將通過消除邊緣得到的，因爲如果低於邊子樹其中有k個節點，溢出將是（k，n - k）。因此，您可以通過遍歷所有節點並尋找最平均地平衡（k，n-k）的節點來找到最佳切分。

計算節點需要O（n）個時間，並且運行遞歸訪問每個節點和邊最多O（1）次，因此也需要O（n）時間。尋找最佳切割需要額外的O（n）時間，對於O（n）的淨運行時間。由於我們需要存儲子樹節點計數，所以我們也需要O（n）存儲器。

希望這會有所幫助！

來源

2011-11-24 20:25:53 templatetypedef

你找不到任何算法來做到這一點。 –

@ SaeedAmiri-對不起，你能詳細說明一下嗎？ – templatetypedef

我沒有看到最大程度的大小3，正確。 –

如果你看到我對Divide-And-Conquer Algorithm for Trees的回答，你可以看到我會找到一個節點把樹分成2個幾乎相等大小的樹（自下而上的算法），現在你只需要選擇這個節點的一個邊來做你想做的事。

您目前的做法是行不通的假設你有一個完全二叉樹，現在加入到葉子（命名爲bad葉），您的最長路徑將是一個其他的葉子到最後的一個範圍內的一個長3*log n的路徑的路徑與此bad葉相連，並且您的中間邊緣將位於此路徑內（事實上，在您通過壞葉之後），並且如果您基於此邊進行分區，則會有一部分O(log n)，另一部分大小爲O(n)。

來源

2011-11-24 20:55:24

將樹拆分成相等部分

回答

相關問題