Prim算法-最小生成树算法

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

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

在每一步中, 它都会考虑所有边缘并选择最小重量的边缘。拾取边缘后, 它将边缘的另一个端点移动到包含MST的集合。
使用普里姆算法查找MST的步骤：

创建MST集, 以跟踪已包含在MST中的顶点。
将键值分配给输入图中的所有顶点。将所有键值初始化为INFINITE（∞）。为第一个顶点分配键值, 例如0, 以便首先选择它。
虽然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 vertexRoot = 0Adj [0] = 5, 1Parent, π [5] = 0 and π [1] = 0Key [5] = ∞ and key [1] = ∞w [0, 5) = 10and w (0, 1) = 28w (u, v) < key [5] , w (u, v) < key [1]Key [5] = 10 and key [1] = 28So 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 heapTaking 4, key [4] = ∞π [4] = 5(u, v) < key [v] then key [4] = 25w (5, 4) = 25w (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) = 22w (4, 6) = 24w (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 = 3i.e.22 < 24

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

文章图片

Adj [3] = {4, 6, 2}4 is already in heap4 ≠ Q key [6] = 24 now becomes key [6] = 18Key [2] = ∞key [6] = 24w (3, 2) = 12w (3, 6) = 18w (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 < 18Now the root is 2 Adj [2] = {3, 1}3 is already in a heapTaking 1, key [1] = 28w (2, 1) = 16w (2, 1) < key [1]

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