Data Structures Algorithms 简明教程

Prim’s Minimal Spanning Tree

普里姆最小生成树算法是查找图的最小生成树的有效方法之一。最小生成树是一个子图，它使用最少的边和最少的成本（分配给每条边的权重的和）连接主图中存在的所有顶点。

与任何最短路径算法类似，该算法从设置为主根的顶点开始，并通过确定成本最低的邻接边遍历图中的所有顶点。

spanning tree of graph

Prim’s Algorithm

要执行 prim 算法，算法需要的输入是图 G {V, E}（其中 V 是顶点集，E 是边集）和源顶点 S。图 G 的最小生成树作为输出获得。

Algorithm

  1. 声明一个数组 visited[] 来存储已访问的顶点，首先将任意根（例如 S）添加到 visited 数组中。

  2. 检查最后一个已访问顶点的相邻顶点是否存在于 visited[] 数组中。

  3. 如果顶点不在 visited[] 数组中，请比较边的成本并将成本最低的边添加到输出生成树中。

  4. 将具有最小成本边的相邻未访问顶点添加到 visited[] 数组中，并将最小成本边添加到最小生成树输出中。

  5. 对图中的所有未访问顶点重复步骤 2 和 4，以获得给定图的完整最小生成树输出。

  6. 计算获得的最小生成树的成本。

Examples

  1. 根据 S 作为任意根的给定图形使用 Prim 方法（贪心方法）找到最小生成树。

prims minimum spanning tree

Solution

Step 1

创建一个已访问数组来存储所有已访问的顶点。

V = { }

任意的根被提及为 S，所以在所有连接到 S 的边中，我们需要找到成本最低的边。

S → B = 8
V = {S, B}
s to b

Step 2

因为 B 是最后访问的，所以检查连接到顶点 B 的成本最低的边。

B → A = 9
B → C = 16
B → E = 14

因此，B → A 是添加到生成树中的边。

V = {S, B, A}
b to a

Step 3

因为 A 是最后访问的，检查与顶点 A 连接的最低成本边。

A → C = 22
A → B = 9
A → E = 11

但是，A→ B 已经包含在生成树中，检查下一个最低成本边。因此，A→ E 被添加到生成树中。

V = {S, B, A, E}
a to e

Step 4

因为 E 是最后访问的，检查连接到顶点 E 的成本最低的边。

E → C = 18
E → D = 3

因此，E→ D 被添加到生成树中。

V = {S, B, A, E, D}
e to d

Step 5

因为 D 是最后访问的，检查与顶点 D 连接的最低成本边。

D → C = 15
E → D = 3

因此，D→ C 被添加到生成树中。

V = {S, B, A, E, D, C}
d to c

采用最低成本获得最小生成树 = 46

Example

最终，程序执行 Prim 的最小生成树问题，它将成本邻接矩阵作为输入，并将生成树作为输出打印出来，连同最低成本一起。