Prim算法-最小生成树算法

这是一个贪婪的算法。它从一棵空的生成树开始。这个想法是维护两组顶点：

• 包含MST中已经包含的顶点。
• 包含尚未包含的顶点。

在每一步中, 它都会考虑所有边缘并选择最小重量的边缘。拾取边缘后, 它将边缘的另一个端点移动到包含MST的集合。

使用普里姆算法查找MST的步骤：

1. 创建MST集, 以跟踪已包含在MST中的顶点。
2. 将键值分配给输入图中的所有顶点。将所有键值初始化为INFINITE（∞）。为第一个顶点分配键值, 例如0, 以便首先选择它。
3. 虽然MST集不包括所有顶点。选择未设置MST且具有最小键值的顶点u。在MST集中包含“ u”。更新u的所有相邻顶点的键值。要更新, 请迭代所有相邻的顶点。对于每个相邻顶点v, 如果边缘u.v的权重小于v的先前键值, 则将键值更新为u.v的权重。

MST-PRIM (G, w, r)
 1. for each u ∈ V [G]
 2. do key [u] ← ∞
 3. π [u] ← NIL
 4. key [r] ← 0
 5. Q ← V [G]
 6. While Q ? ∅
 7. do u ← EXTRACT - MIN (Q)
 8. for each v ∈ Adj [u]
 9. do if v ∈ Q and w (u, v) < key [v]
 10. then π [v] ← u
 11. key [v] ← w (u, v) 

示例：使用Prim算法为下图生成最小成本生成树。

解决方案：在Prim的算法中, 首先我们将优先级队列Q.初始化为将所有顶点以及每个顶点的键包含到∞中（除了根, 其键设置为0）。假设0个顶点是根, 即r。通过EXTRACT-MIN（Q）过程, 现在u = r且Adj [u] = {5, 1}。

从集合Q中删除u并将其添加到树中顶点的集合V-Q中。现在, 更新与u相邻但不在树中的每个顶点v的键和π字段。

Taking 0 as starting vertex
  Root = 0
    Adj [0] = 5, 1
  Parent, π [5] = 0 and π [1] = 0
      Key [5] = ∞ and key [1] = ∞
  w [0, 5) = 10  and w (0, 1) = 28
   w (u, v) < key [5] , w (u, v) < key [1]
        Key [5] = 10 and key [1] = 28
So update key value of 5 and 1 is:

现在通过EXTRACT_MIN（Q）删除5, 因为键[5] = 10（最小值）, 所以u = 5。

Adj [5] = {0, 4} and 0 is already in heap
  Taking 4, key [4] = ∞      π [4] = 5
  (u, v) < key [v] then key [4] = 25
  w (5, 4) = 25
  w (5, 4) < key [4]
Update key value and parent of 4.

现在删除4, 因为键[4] = 25（最小值）, 所以u = 4

Adj [4] = {6, 3}
   Key [3] = ∞         key [6] = ∞
   w (4, 3) = 22        w (4, 6) = 24
   w (u, v) < key [v]    w (u, v) < key [v]
   w (4, 3) < key [3]      w (4, 6) < key [6]

将键[3]的键值更新为22, 将键[6]的键值更新为24。

3、6的父级为4。

π[3]= 4       π[6]= 4

u = EXTRACT_MIN (3, 6)            [key [3] < key [6]]
u = 3              i.e.  22 < 24

现在删除3, 因为键[3] = 22为最小值, 所以u = 3。

Adj [3] = {4, 6, 2}
  4 is already in heap
  4 ≠ Q key [6] = 24 now becomes key [6] = 18
  Key [2] = ∞            key [6] = 24
  w (3, 2) = 12          w (3, 6) = 18
  w (3, 2) < key [2]         w (3, 6) < key [6]

现在在Q中, 键[2] = 12, 键[6] = 18, 键[1] = 28, 并且2和6的父级是3。

π [2] = 3      π[6]=3

现在由EXTRACT_MIN（Q）删除2, 因为键[2] = 12是最小的。

u = EXTRACT_MIN (2, 6)
u = 2          [key [2] < key [6]]
        12 < 18
Now the root is 2 
Adj [2] = {3, 1}
   3 is already in a heap
Taking 1, key [1] = 28
   w (2, 1) = 16
   w (2, 1) < key [1]

因此, 将键[1]的键值更新为16, 将其父键的值更新为2。

π[1]= 2

现在通过EXTRACT_MIN（Q）删除1, 因为键[1] = 16是最小的。

Adj [1] = {0, 6, 2}
    0 and 2 are already in heap.
Taking 6, key [6] = 18
   w [1, 6] = 14
   w [1, 6] < key [6]

将键值6更新为14, 其父键更新为1。

Π [6] = 1

现在, 所有顶点都已生成, 使用表格上方的, 我们得到了最小生成树。

0 → 5 → 4 → 3 → 2 → 1 → 6
[Because Π [5] = 0, Π [4] = 5, Π [3] = 4, Π [2] = 3, Π [1] =2, Π [6] =1]

因此, 最后的生成树是

总费用= 10 + 25 + 22 + 12 + 16 + 14 = 99