樹中的最小費用邊刪除將樹中的所有樹葉分開

這是一個更大的問題，我已經歸結爲以下問題。給定具有正邊權重的加權樹，並且具有k個葉子。葉子是一個節點，它恰好在樹中有一個相鄰的節點。我需要從樹中刪除一些邊，以便將樹分解爲k個分量，每個分量恰好包含原始樹中的一個葉節點。換句話說，我需要刪除邊緣，以便原始樹中的所有樹葉都與原始樹的其他樹葉分離/斷開。樹中的最小費用邊刪除將樹中的所有樹葉分開

我需要這樣做，使刪除邊的權重（成本）的總和最小化。顯示k-1邊緣需要被刪除是微不足道的。所以我需要最小化這些k-1邊的權重總和。

這樣做的最佳方式是什麼？任何提示將不勝感激。謝謝！

來源

2012-10-06 Paresh

我認爲貪婪的算法在這裏工作。

即，刪除生成新組件並重復k-1次的最低權重邊。

請注意，你必須要小心的圖形，如：

d < -A-> B-> C^

如果您先刪除B-> C，然後刪除A-> B不會生成新的組件，因爲B不是葉，所以不需要分離。

換句話說，當選擇最低權重邊緣時，不要包含任何仍不會導致葉節點的邊緣。

來源

2012-10-06 19:31:18

謝謝！我不確定貪婪解決方案是否確實有效。另外，這在速度方面是最佳的嗎？這將在最壞的情況下花費O（kn）時間，k是樹葉的數量，n是節點的數量。從每個k-1葉子（k中的任何k-1）運行DFS，並從中找到與其連接的任何其他葉子的最小權重邊緣。刪除這樣的邊（在其他葉的路徑上）將確保生成新的組件。有更快的方法嗎？再次感謝！ – Paresh

我認爲一個快速的解決方案將按照權重O（nlogn）的順序預先設置邊緣。我認爲你可以通過刪除任何節點來刪除壞邊緣，這些節點在刪除最低權重邊緣時會成爲新的葉節點。爲了有效地做到這一點，可能有助於在每個節點中存儲父指針。 –

如果您刪除新創建的葉子，它們又可能會創建新的葉子。因此，要刪除壞邊，這種刪除需要繼續，直到我們沒有在兩個新生成的組件中留下任何葉子，這些組件在邊刪除之前沒有葉節點不存在。這基本上是一個DFS。我錯過了什麼嗎？順便說一句，邊緣不是直接的，所以識別父母是微不足道的。 – Paresh

樹中的最小費用邊刪除將樹中的所有樹葉分開

回答

相關問題