多重最小生成樹圖

Question

我被困在一個條件。我想知道一個圖可以有多個最小生成樹的情況是什麼？ 任何人都可以幫助我嗎？

Answer 1

我回答的假設是你有一個邊緣權重圖，並想知道是否有任何其他MST存在。

您可以通過以下方法做到這一點：

1. 查找具有相同的重量MST其他一些邊緣在MST不邊緣。 例如，假設邊（a，b）在MST中並且具有等於邊（c，d）的權重。

2. 從圖中刪除邊（a，b）並再次運行MST。

3. 重複上述步驟直至找不到其他此類邊緣或MST具有相同的總重量。

記住一個圖有不同的MST，至少兩個邊必須相等。