Data Structures Algorithms 简明教程
Kruskal’s Minimal Spanning Tree Algorithm
克鲁斯卡尔的最小生成树算法是寻找图的最小生成树的高效方法之一。最小生成树是连接主图中所有当前顶点的子图，并且具有尽可能少的边和最小的代价（分配给每条边的权重总和）。
该算法首先从林开始——定义为只包含主图中顶点的子图——图的林，随后添加最小代价的边，直到创建出最小生成树，而不会在图中形成环。
克鲁斯卡尔算法的实现比普里姆算法更简单，但复杂度更高。
Kruskal’s Algorithm
克鲁斯卡尔算法的输入是图 G {V, E}，其中 V 是顶点集，E 是边集，以及源顶点 S，图 G 的最小生成树作为输出获得。
Algorithm
-
按升序对图中的所有边进行排序，并将它们存储在数组 edge[] 中。
-
构建平面图的森林，其中包含所有顶点。
-
从 edge[] 数组中选择代价最小的边，并将其添加到图的森林中。将访问过的顶点标记为并将其添加到 visited[] 数组中。
-
重复步骤 2 和 3，直到访问所有顶点，而不会在图中形成任何环
-
当访问所有顶点，最小生成树形成时。
-
计算形成的输出生成树的最小代价。
Solution
第一步，按升序对给定图中的所有边进行排序，并将值存储在数组中。
然后，在单个平面上构建给定图的森林。
从排序的边代价列表中，选择代价最小的边，并将其添加到输出图中的森林中。
B → D = 5
Minimum cost = 5
Visited array, v = {B, D}
类似地，下一个代价最小的边是 B → A = 6；所以我们将其添加到输出图中。
Minimum cost = 5 + 6 = 11
Visited array, v = {B, D, A}
下一个代价最小的边是 C → F = 9；将其添加到输出图中。
Minimum Cost = 5 + 6 + 9 = 20
Visited array, v = {B, D, A, C, F}
下一个将添加到输出图中的边是 F → E = 10。
Minimum Cost = 5 + 6 + 9 + 10 = 30
Visited array, v = {B, D, A, C, F, E}
从最小代价数组中的下一个分支是 B → C = 11，因此我们将其添加到输出图中。
Minimum cost = 5 + 6 + 9 + 10 + 11 = 41
Visited array, v = {B, D, A, C, F, E}
最小代价数组中添加到输出图的最后一条分支是 F → G = 12。
Minimum cost = 5 + 6 + 9 + 10 + 11 + 12 = 53
Visited array, v = {B, D, A, C, F, E, G}
获得的结果是给定图的最小生成树，代价 = 53。