最小生成樹

習題預習

1. 給定一個加權無向圖，找出最小生成樹。
2. 給定一個電信網路，每個城市都有一個信箱，找出最小的花費，使每個城市都可以通過信箱與其他城市通信。
3. 給定一個道路網絡，找出最小的花費，使得所有城市之間都可以到達。
4. 給定一個海底電纜網絡，找出最小的花費，使得所有島嶼都可以通過電纜聯繫。
5. 給定一個管道網絡，找出最小的花費，使得所有城市都可以通過管道連接。

說明知識

最小生成樹 (Minimum Spanning Tree) 是一個常見的圖論問題，用途很廣，例如查找最小路徑以及網絡優化等。

在一個連通加權無向圖中，由於不需要環，因此可以找到一個包含所有節點且權值和最小的生成樹。此時，這棵樹的節點數目與原圖的節點數目相同，但邊數少於原圖。這棵樹稱為最小生成樹。

最小生成樹有很多種求解方法，例如 Kruskal 演算法、Prim 演算法和 Boruvka 演算法等。在求解最小生成樹的過程中，演算法將查找許多樹的比較來找到其權值和最小的樹。

以下是一個簡單的例子，其中求解以下圖的 MST：

Kruskal演算法的步驟如下：

1. 按權值升序排序所有的邊。
2. 將每個節點都標記為一個不同的集合。
3. 從權值最小的邊開始，如果這條邊連接的兩個點不在同一個集合中，就加入MST，否則捨棄。（這條邊不可能形成環，因為如果形成環，就會有另一條邊的權值更小，這就違反了排序之後的邏輯）
4. 重複步驟3直到形成MST。

Kruskal演算法應用在圖中之後，下面的圖就是 MST：

彙總重點

以下是Minimum Spanning Trees的重點：

1. 最小生成樹是一個連通圖，其中每個節點都和其他節點相連。

2. 最小生成樹的邊權值之和最小。

3. 最小生成樹可能不唯一。

4. Kruskal和Prim算法是求最小生成樹的兩種常見方法。

5. Kruskal算法是按照權值從小到大的順序，依次選擇邊加入最小生成樹中，直到所有節點都連通。

6. Prim算法是從一個節點開始，按照權值從小到大的順序，選擇連接已選擇節點和未選擇節點的邊，直到所有節點都連通。

7. Kruskal算法的時間複雜度是O(E log E)，Prim算法的時間複雜度是O(E log V)。

8. 最小生成樹可以用來解決一些最小花費問題，如最小成本網絡流等。

知識測驗

1. 一個圖形有n個節點，以及它們之間的權重，請求最小生成樹的權重。

答案：這個問題沒有確定的答案，因為結果取決於給定圖形的權重和邊數。

2. 求一個包含n個節點的圖形的最小生成樹。

答案：使用Kruskal或Prim算法可以找到一個包含n個節點的圖形的最小生成樹。

3. 在一個完全圖形中，邊權重是亂數生成的，請使用Kruskal或Prim算法找到最小生成樹。

答案：這個問題的答案取決於圖形的節點數量和邊權重，因此沒有確定的答案。

4. 在一個拓撲圖形中，給定每個邊的權重，求最小生成樹的權重。

答案：使用Kruskal或Prim算法可以找到一個包含n個節點的圖形的最小生成樹。

5. 求一個無向圖形的生成樹，使得最長邊的權重最小。

答案：這個問題可以通過將邊權重的負值取反，然後使用Kruskal或Prim算法找到最小生成樹。