技术图文：如何利用C# 实现 Kruskal 最小生成树算法？

背景

以前我写过一些图文来介绍有关数据结构与算法的知识：

• 8大排序算法之：直接插入排序（Straight Insertion Sort）
• 8大排序算法之：希尔插入排序（Shell Insertion Sort）
• 8大排序算法之：直接选择排序（Straight Selection Sort）
• 8大排序算法之：堆选择排序（Heap Selection Sort）
• 8大排序算法之：冒泡排序（Bubble ExchangeSort）
• 8大排序算法之：快速交换排序（Quick Exchange Sort）
• 8大排序算法之：并归排序（Merge Sort）
• 8大排序算法之：桶排序（Bucket Sort）
• 8大搜索算法之：顺序搜索
• 8大搜索算法之：二分搜索
• 8大搜索算法之：插补搜索
• 8大搜索算法之：二叉搜索树（上）
• 8大搜索算法之：二叉搜索树（中）
• 8大搜索算法之：二叉搜索树（下）
• 8大搜索算法之：AVL树（上）
• 8大搜索算法之：AVL树（中）
• 8大搜索算法之：AVL树（下）
• 8大搜索算法之：红黑树（上）
• 8大搜索算法之：红黑树（中）
• 8大搜索算法之：红黑树（下）

本次，向大家介绍图论中构造最小生成树的 Kruskal 算法。

技术分析

Kruskal 算法：

例子：

该例子演示了一个含有6个结点，10条边的连通网，通过 Kruskal 算法逐步演化为含有6个结点，5条边的连通子网的过程，即构造最小生成树的过程。

代码实现

Step1 构造边表结点的结构 EdgeNode。

public class EdgeNode
{/// <summary>/// 获取边终点在顶点数组中的位置/// </summary>public int Index { get; }/// <summary>/// 获取边上的权值/// </summary>public double Weight { get; }/// <summary>/// 获取或设置下一个邻接点/// </summary>public EdgeNode Next { get; set; }/// <summary>/// 初始化EdgeNode类的新实例/// </summary>/// <param name="index">边终点在顶点数组中的位置</param>/// <param name="weight">边上的权值</param>/// <param name="next">下一个邻接点</param>public EdgeNode(int index, double weight = 0.0, EdgeNode next = null){if (index < 0)throw new ArgumentOutOfRangeException();Index = index;Weight = weight;Next = next;}
}

Step2 构造顶点表结点的结构 VertexNode。

public class VertexNode
{/// <summary>/// 获取或设置顶点的名字/// </summary>public string VertexName { get; set; }/// <summary>/// 获取或设置顶点是否被访问/// </summary>public bool Visited { get; set; }/// <summary>/// 获取或设置顶点的第一个邻接点/// </summary>public EdgeNode FirstNode { get; set; }/// <summary>/// 初始化VertexNode类的新实例/// </summary>/// <param name="vName">顶点的名字</param>/// <param name="firstNode">顶点的第一个邻接点</param>public VertexNode(string vName, EdgeNode firstNode = null){VertexName = vName;Visited = false;FirstNode = firstNode;}
}

Step3 构造利用邻接表存储图的结构AdGraph。

通过 AdGraph 的索引器可以为顶点表赋值，通过 AddEdge 方法可以为边表赋值。

public class AdGraph
{private readonly VertexNode[] _vertexList; //结点表/// <summary>/// 获取图的结点数/// </summary>public int VertexCount { get; }/// <summary>/// 初始化AdGraph类的新实例/// </summary>/// <param name="vCount">图中结点的个数</param>public AdGraph(int vCount){if (vCount <= 0)throw new ArgumentOutOfRangeException();VertexCount = vCount;_vertexList = new VertexNode[vCount];}/// <summary>/// 获取或设置图中各结点的名称/// </summary>/// <param name="index">结点名称从零开始的索引</param>/// <returns>指定索引处结点的名称</returns>public string this[int index]{get{if (index < 0 || index > VertexCount - 1)throw new ArgumentOutOfRangeException();return _vertexList[index] == null? "NULL": _vertexList[index].VertexName;}set{if (index < 0 || index > VertexCount - 1)throw new ArgumentOutOfRangeException();if (_vertexList[index] == null)_vertexList[index] = new VertexNode(value);else_vertexList[index].VertexName = value;}}/// <summary>/// 得到结点在结点表中的位置/// </summary>/// <param name="vertexName">结点的名称</param>/// <returns>结点的位置</returns>private int GetIndex(string vertexName){int i;for (i = 0; i < VertexCount; i++){if (_vertexList[i] != null && _vertexList[i].VertexName == vertexName)break;}return i == VertexCount ? -1 : i;}/// <summary>/// 给图加边/// </summary>/// <param name="startVertexName">起始结点的名字</param>/// <param name="endVertexName">终止结点的名字</param>/// <param name="weight">边上的权值</param>public void AddEdge(string startVertexName, string endVertexName, double weight = 0.0){int i = GetIndex(startVertexName);int j = GetIndex(endVertexName);if (i == -1 || j == -1)throw new Exception("图中不存在该边.");EdgeNode temp = _vertexList[i].FirstNode;if (temp == null){_vertexList[i].FirstNode = new EdgeNode(j, weight);}else{while (temp.Next != null)temp = temp.Next;temp.Next = new EdgeNode(j, weight);}}
}    

上面例子对应的邻接表如下所示：

Step4 构造最小生成树结点的结构 SpanTreeNode。

public class SpanTreeNode
{/// <summary>/// 获取或设置结点本身的名称/// </summary>public string SelfName { get; }/// <summary>/// 获取或设置结点双亲的名称/// </summary>public string ParentName { get; }/// <summary>/// 获取或设置边的权值/// </summary>public double Weight { get; set; }/// <summary>/// 构造SpanTreeNode实例/// </summary>/// <param name="selfName">结点本身的名称</param>/// <param name="parentName">结点双亲的名称</param>/// <param name="weight">边的权值</param>public SpanTreeNode(string selfName, string parentName, double weight){if (string.IsNullOrEmpty(selfName) || string.IsNullOrEmpty(parentName))throw new ArgumentNullException();SelfName = selfName;ParentName = parentName;Weight = weight;}
}

Step5 构造边的结构 Edge。

internal class Edge
{/// <summary>/// 起点编号/// </summary>public int Begin { get;}/// <summary>/// 终点编号/// </summary>public int End { get; }/// <summary>/// 权值/// </summary>public double Weight { get; }/// <summary>/// 创建一个 Edge 类的新实例/// </summary>/// <param name="begin">起点编号</param>/// <param name="end">终点编号</param>/// <param name="weight">权值</param>public Edge(int begin, int end, double weight = 0.0){Begin = begin;End = end;Weight = weight;}
}

Step6 获取边集合的方法 GetEdges。

private Edge[] GetEdges()
{for (int i = 0; i < VertexCount; i++)_vertexList[i].Visited = false;List<Edge> result = new List<Edge>();for (int i = 0; i < VertexCount; i++){_vertexList[i].Visited = true;EdgeNode p = _vertexList[i].FirstNode;while (p != null){if (_vertexList[p.Index].Visited == false){Edge edge = new Edge(i, p.Index, p.Weight);result.Add(edge);}p = p.Next;}}return result.OrderBy(a => a.Weight).ToArray();
}

上面例子对应的边的集合如下所示：

Step7 获取最小生成树的 Kruskal 算法。

private int Find(int[] parent, int f)
{while (parent[f] > 0)f = parent[f];return f;
}/// <summary>
/// 克鲁斯卡尔算法 最小生成树
/// </summary>
/// <returns></returns>
public SpanTreeNode[] MiniSpanTree()
{int[] parent = new int[VertexCount];for (int i = 0; i < VertexCount; i++){parent[i] = 0;}SpanTreeNode[] tree = new SpanTreeNode[VertexCount];int count = 0;Edge[] edges = GetEdges();for (int i = 0; i < edges.Length; i++){int begin = edges[i].Begin;int end = edges[i].End;int n = Find(parent, begin);int m = Find(parent, end);if (n != m){if (i == 0){tree[count] = new SpanTreeNode(_vertexList[begin].VertexName, "NULL", 0.0);count++;}parent[n] = m;tree[count] = new SpanTreeNode(_vertexList[end].VertexName,_vertexList[begin].VertexName, edges[i].Weight);count++;}}return tree;
}

总结

到此为止代码部分就全部介绍完了，我们来看一下上面例子的应用。

static void Main(string[] args)
{AdGraph alg = new AdGraph(6);alg[0] = "V0";alg[1] = "V1";alg[2] = "V2";alg[3] = "V3";alg[4] = "V4";alg[5] = "V5";alg.AddEdge("V0", "V1", 6);alg.AddEdge("V0", "V2", 1);alg.AddEdge("V0", "V3", 5);alg.AddEdge("V1", "V0", 6);alg.AddEdge("V1", "V2", 5);alg.AddEdge("V1", "V4", 3);alg.AddEdge("V2", "V0", 1);alg.AddEdge("V2", "V1", 5);alg.AddEdge("V2", "V3", 7);alg.AddEdge("V2", "V4", 5);alg.AddEdge("V2", "V5", 4);alg.AddEdge("V3", "V0", 5);alg.AddEdge("V3", "V2", 7);alg.AddEdge("V3", "V5", 2);alg.AddEdge("V4", "V1", 3);alg.AddEdge("V4", "V2", 5);alg.AddEdge("V4", "V5", 6);alg.AddEdge("V5", "V2", 4);alg.AddEdge("V5", "V3", 2);alg.AddEdge("V5", "V4", 6);SpanTreeNode[] tree = alg.MiniSpanTree();double sum = 0;for (int i = 0; i < tree.Length; i++){string str = "(" + tree[i].ParentName + ","+ tree[i].SelfName + ") Weight:"+ tree[i].Weight;Console.WriteLine(str);sum += tree[i].Weight;}Console.WriteLine(sum);
}

我们再通过一个例子来演示如何应用：

上面是一幅纽约市附近的地图，对应的数据存储在 graph.txt 文件中。

读入该文件，构造好 AdGraph 结构后，调用我们写好的 Kruskal 算法，得到的结果如下：

是不是很有趣，今天就到这里吧！马上要放假了，我们的招新活动也即将开启，希望大家关注呦！

See You！

相关图文：

• 如何利用 C# 实现 K 最邻近算法？
• 如何利用 C# 实现 K-D Tree 结构？
• 如何利用 C# + KDTree 实现 K 最邻近算法？
• 如何利用 C# 对神经网络模型进行抽象？
• 如何利用 C# 实现神经网络的感知器模型？
• 如何利用 C# 实现 Delta 学习规则？
• 如何利用 C# 爬取带 Token 验证的网站数据？
• 如何利用 C# 向 Access 数据库插入大量数据？
• 如何利用 C# 开发「桌面版百度翻译」软件！
• 如何利用 C# 开发「股票数据分析软件」（上）
• 如何利用 C# 开发「股票数据分析软件」（中）
• 如何利用 C# 开发「股票数据分析软件」（下）
• 如何利用 C# 爬取「财报说」中的股票数据？
• 如何利用 C# 爬取 One 持有者返利数据！
• 如何利用 C# 爬取Gate.io交易所的公告！
• 如何利用 C# 爬取BigOne交易所的公告！
• 如何利用 C# 爬取 ONE 的交易数据？
• 如何利用 C# 爬取「猫眼电影：热映口碑榜」及对应影片信息！
• 如何利用 C# 爬取「猫眼电影专业版：票房」数据！
• 如何利用 C# 爬取「猫眼电影：最受期待榜」及对应影片信息！
• 如何利用 C# 爬取「猫眼电影：国内票房榜」及对应影片信息！
• 如何利用 C# + Python 破解猫眼电影的反爬虫机制？
• 如何利用BigOne的API制作自动化交易系统 – 身份验证
• 如何利用BigOne的API制作自动化交易系统 – 获取账户资产
• 如何利用BigOne的API制作自动化交易系统 – 订单系统