普利姆演算法

習題預習

1. 使用Prim’s演算法來尋找一個帶有權重邊的最小生成樹，請問這個演算法的時間複雜度為何？
2. 請問在Prim’s演算法中，如何選擇下一個要加入最小生成樹的節點？
3. 假設有一個帶有權重邊的無向圖，請問是否一定存在一個帶有權重邊的最小生成樹？
4. 如果在Prim’s演算法的過程中，所有邊的權重都相同，最小生成樹可能有多個嗎？
5. 在Prim’s演算法中，如何判斷一個圖是連通的？

說明知識

Prim的演算法是一種用於尋找最小生成樹的貪婪演算法。

簡單來說，Prim演算法通過從一個起點開始，選擇邊的方式來構建一個最小生成樹。演算法開始時，選擇任意一點作為起點，然後選取與該起點相連的最小權值邊，a和b兩個點在生成樹上，沒有其他的路線能夠從a和b這兩個點達到，接著選擇與a或b相連的點到生成樹上（由於是連到a或b點，最小權值邊的選擇是唯一的），此過程迭代直到生成樹中包含了所有頂點。

例如，考慮下圖：

      C
    / | \
  3/  |2\  \4
  A---F---B
  2\  |5/  /3
    \ | / 
      D

從節點A開始，該該節點被添加到生成樹中。 節點A與節點F之間的邊（權值為2）是包含節點A的最小權值邊，添加節點F。節點A與節點C之間的邊（權值為3）是包含節點A的最小權值邊，添加節點C。 節點F與節點B之間的邊（權值為2）是包含節點B，F的最小權值邊，添加節點B。 節點F與節點D之間的邊（權值為5）是包含節點B、F、D的最小權值邊，添加節點D。 節點F與節點E之間的邊（權值為4）是包含節點B、F、E、D的最小權值邊，添加節點E。

最終生成樹如下所示：

      C
      |
  (3) A
      |
      F
    / | \
  2/  |  \2
  B   E   D

彙總重點

• Prim’s Algorithm是一種用來找尋最小生成樹的演算法。
• 演算法通常需要一個起始點，從該起始點開始建立最小生成樹。
• 演算法維護兩個數據結構，分別是集合S和邊集合T。S表示已經在最小生成樹上的點，而T則表示已經在最小生成樹上的邊。
• 首先將起始點加入集合S中。
• 從集合S中的所有點開始找尋最小生成樹的下一個邊，找到其中最小權重的邊並加入邊集合T中。
• 將邊的兩個端點中未被加入集合S中的點加入集合S中，重複上述過程，直到所有點都在集合S中。
• Prim’s Algorithm的時間複雜度為O(E log V)，其中E是邊的數量，V是點的數量。

知識測驗

1. 給定以下未經排序的圖形的邊權重，求 Prim’s 算法找到的最小生成樹的權重總和：

    A --2-- B --1-- C
   /    |       /    |
 8     3     1     5
 /      |     /      |
D --2-- E --4-- F --3-- G

答案：11

2. 給定以下未經排序的圖形的邊權重，求 Prim’s 算法找到的最小生成樹的權重總和：

    A --2-- B --1-- C --2-- D
   /    |       /    |       |
 3     1     6     3     4
 /      |     /      |      |
E --5-- F --2-- G --5-- H --3-- I

答案：13

3. 給定以下未經排序的圖形的邊權重，求 Prim’s 算法找到的最小生成樹的權重總和：

    A --2-- B --1-- C --2-- D --3-- E
   /    |       /    |      |       |
 7     6     1     2     8      5
 /      |     /      |     /        |
F --3-- G --4-- H --10-- I --2-- J --1-- K

答案：16

4. 給定以下未經排序的圖形的邊權重，求 Prim’s 算法找到的最小生成樹的權重總和：

     A --3-- B --1-- C --2-- D --5-- E
    /    |       /    |      |       |
  10    2     5     4     7      8
  /      |     /      |     /        |
 F --8-- G --3-- H --1-- I --2-- J --4-- K

答案：19

5. 給定以下未經排序的圖形的邊權重，求 Prim’s 算法找到的最小生成樹的權重總和：

       A --2-- B --1-- C --2-- D --3-- E
      /    |       /    |      |      |
    8     10    6     2     1     2
   /      |     /      |     /       |
 F --3-- G --4-- H --7-- I --9-- J --3-- K

答案：19