一、Kruskal算法简史

克鲁斯卡尔（Kruskal）算法是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。

二、Kruskal算法思路

（1）记Graph中有v个顶点，e个边；
（2）新建图，拥有原图中相同的e个顶点，但没有边；
（3）将原图中所有e个边按权值从小到大排序；
（4）循环：从权值最小的边开始遍历每条边，直至图中所有的节点都在同一个连通分量中。
如果这条边连接的两个节点于图中不在同一个连通分量中，添加这条边到图中。如此反复。

三、Kruskal算法的源代码

核心代码：

using System;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public class Subset{public int Parent { get; set; } = 0;public int Rank { get; set; } = 0;}/// <summary>/// 最小生成树 Kruskal 算法/// </summary>public static class MST_Kruskal_Algorithm{private static int Find(Subset[] subsets, int i){if (subsets[i].Parent != i){subsets[i].Parent = Find(subsets, subsets[i].Parent);}return subsets[i].Parent;}private static void Union(Subset[] subsets, int x, int y){int xroot = Find(subsets, x);int yroot = Find(subsets, y);if (subsets[xroot].Rank < subsets[yroot].Rank){subsets[xroot].Parent = yroot;}else if (subsets[xroot].Rank > subsets[yroot].Rank){subsets[yroot].Parent = xroot;}else{subsets[yroot].Parent = xroot;subsets[xroot].Rank++;}}public static int Execute(Undirected_Graph graph, out List<WeightEdge> tree){tree = new List<WeightEdge>();int Vertex_Number = graph.Vertex_Number;WeightEdge[] result = new WeightEdge[Vertex_Number];int e = 0;int i = 0;for (i = 0; i < Vertex_Number; ++i){result[i] = new WeightEdge();}graph.EdgeArray.Sort(delegate(WeightEdge a, WeightEdge b) { return a.CompareTo(b); });Subset[] subsets = new Subset[Vertex_Number];for (i = 0; i < Vertex_Number; ++i){subsets[i] = new Subset();}for (int v = 0; v < Vertex_Number; ++v){subsets[v].Parent = v;subsets[v].Rank = 0;}i = 0;while (e < (Vertex_Number - 1)){WeightEdge next_edge = graph.EdgeArray[i++];int x = Find(subsets, next_edge.Start);int y = Find(subsets, next_edge.End);if (x != y){result[e++] = next_edge;Union(subsets, x, y);}}int minimumCost = 0;for (i = 0; i < e; ++i){tree.Add(new WeightEdge(result[i].Start,result[i].End, result[i].Weight));minimumCost += result[i].Weight;}return minimumCost;}}
}

 ——————————————————————

POWER BY 315SOFT.COM &
TRUFFER.CN