Data Structures Algorithms 简明教程
Prim’s Minimal Spanning Tree
普里姆最小生成树算法是查找图的最小生成树的有效方法之一。最小生成树是一个子图，它使用最少的边和最少的成本（分配给每条边的权重的和）连接主图中存在的所有顶点。
Prim’s minimal spanning tree algorithm is one of the efficient methods to find the minimum spanning tree of a graph. A minimum spanning tree is a sub graph that connects all the vertices present in the main graph with the least possible edges and minimum cost (sum of the weights assigned to each edge).
与任何最短路径算法类似，该算法从设置为主根的顶点开始，并通过确定成本最低的邻接边遍历图中的所有顶点。
The algorithm, similar to any shortest path algorithm, begins from a vertex that is set as a root and walks through all the vertices in the graph by determining the least cost adjacent edges.
Prim’s Algorithm
要执行 prim 算法，算法需要的输入是图 G {V, E}（其中 V 是顶点集，E 是边集）和源顶点 S。图 G 的最小生成树作为输出获得。
To execute the prim’s algorithm, the inputs taken by the algorithm are the graph G {V, E}, where V is the set of vertices and E is the set of edges, and the source vertex S. A minimum spanning tree of graph G is obtained as an output.
Algorithm
-
Declare an array visited[] to store the visited vertices and firstly, add the arbitrary root, say S, to the visited array.
-
Check whether the adjacent vertices of the last visited vertex are present in the visited[] array or not.
-
If the vertices are not in the visited[] array, compare the cost of edges and add the least cost edge to the output spanning tree.
-
The adjacent unvisited vertex with the least cost edge is added into the visited[] array and the least cost edge is added to the minimum spanning tree output.
-
Steps 2 and 4 are repeated for all the unvisited vertices in the graph to obtain the full minimum spanning tree output for the given graph.
-
Calculate the cost of the minimum spanning tree obtained.
Examples
-
Find the minimum spanning tree using prim’s method (greedy approach) for the graph given below with S as the arbitrary root.
Solution
Step 1
Step 1
创建一个已访问数组来存储所有已访问的顶点。
Create a visited array to store all the visited vertices into it.
V = { }任意的根被提及为 S，所以在所有连接到 S 的边中，我们需要找到成本最低的边。
The arbitrary root is mentioned to be S, so among all the edges that are connected to S we need to find the least cost edge.
S → B = 8
V = {S, B}
Step 2
Step 2
因为 B 是最后访问的，所以检查连接到顶点 B 的成本最低的边。
Since B is the last visited, check for the least cost edge that is connected to the vertex B.
B → A = 9
B → C = 16
B → E = 14因此，B → A 是添加到生成树中的边。
Hence, B → A is the edge added to the spanning tree.
V = {S, B, A}
Step 3
Step 3
因为 A 是最后访问的，检查与顶点 A 连接的最低成本边。
Since A is the last visited, check for the least cost edge that is connected to the vertex A.
A → C = 22
A → B = 9
A → E = 11但是，A→ B 已经包含在生成树中，检查下一个最低成本边。因此，A→ E 被添加到生成树中。
But A → B is already in the spanning tree, check for the next least cost edge. Hence, A → E is added to the spanning tree.
V = {S, B, A, E}
Step 4
Step 4
因为 E 是最后访问的，检查连接到顶点 E 的成本最低的边。
Since E is the last visited, check for the least cost edge that is connected to the vertex E.
E → C = 18
E → D = 3因此，E→ D 被添加到生成树中。
Therefore, E → D is added to the spanning tree.
V = {S, B, A, E, D}
Step 5
Step 5
因为 D 是最后访问的，检查与顶点 D 连接的最低成本边。
Since D is the last visited, check for the least cost edge that is connected to the vertex D.
D → C = 15
E → D = 3因此，D→ C 被添加到生成树中。
Therefore, D → C is added to the spanning tree.
V = {S, B, A, E, D, C}
采用最低成本获得最小生成树 = 46
The minimum spanning tree is obtained with the minimum cost = 46