如何將一棵樹分割成兩棵子樹

Question

我有一個對稱的二維數組「myMSTdata [] []」，它表示最小生成樹MST的值爲0，如果沒有邊或表示真實值代表邊緣，現在我需要將此樹劃分爲兩個子樹（part1，part2），其中切割標準是最大權重的邊。然後反覆保留對較大尺寸子樹（意味着具有更多節點數的子樹）進行分區，直到較大尺寸子樹中剩餘的節點數爲K.

Answer 1

建議對這種操作使用鄰接列表由於

1. 你需要單獨的頂點反覆
2. 邊緣<數$ n $的頂點數量。
3. 大運行時間的好處。

我可以知道您正在查看的複雜性嗎？

如果您對任何複雜性感到滿意，我會建議重複的DFS，因爲您正在使用樹，重複的DFS將覆蓋所有邊緣&頂點。在最壞的情況下，運行時間大約爲O（n^2）。