背景

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

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 算法：

Krusal算法

例子：

例子

该例子演示了一个含有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制作自动化交易系统 -- 订单系统