最小生成树算法利用什么算法实现（技术图文如何利用C）

背景

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

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

最小生成树算法利用什么算法实现（技术图文如何利用C）(1)

Krusal算法

例子：

最小生成树算法利用什么算法实现（技术图文如何利用C）(2)

例子

该例子演示了一个含有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); } } }

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

最小生成树算法利用什么算法实现（技术图文如何利用C）(3)

邻接表

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(); }

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

最小生成树算法利用什么算法实现（技术图文如何利用C）(4)

边

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); }

最小生成树算法利用什么算法实现（技术图文如何利用C）(5)