一、Kruskal算法簡史

克魯斯卡爾（Kruskal）算法是一種用來尋找最小生成樹的算法，由Joseph Kruskal在1956年發(fā)表。用來解決同樣問題的還有Prim算法和Boruvka算法等。三種算法都是貪婪算法的應用。和Boruvka算法不同的地方是，Kruskal算法在圖中存在相同權值的邊時也有效。

二、Kruskal算法思路

（1）記Graph中有v個頂點，e個邊；
（2）新建圖，擁有原圖中相同的e個頂點，但沒有邊；
（3）將原圖中所有e個邊按權值從小到大排序；
（4）循環(huán)：從權值最小的邊開始遍歷每條邊，直至圖中所有的節(jié)點都在同一個連通分量中。
如果這條邊連接的兩個節(jié)點于圖中不在同一個連通分量中，添加這條邊到圖中。如此反復。

三、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