首页 > 代码库 > 经典算法题每日演练——第十六题 Kruskal算法
经典算法题每日演练——第十六题 Kruskal算法
原文:经典算法题每日演练——第十六题 Kruskal算法
View CodeView CodeView Code
这篇我们看看第二种生成树的Kruskal算法，这个算法的魅力在于我们可以打一下算法和数据结构的组合拳，很有意思的。
一：思想
若存在M={0,1,2,3,4,5}这样6个节点，我们知道Prim算法构建生成树是从”顶点”这个角度来思考的，然后采用“贪心思想”
来一步步扩大化，最后形成整体最优解，而Kruskal算法有点意思，它是站在”边“这个角度在思考的，首先我有两个集合。
1. 顶点集合(vertexs)：
比如M集合中的每个元素都可以认为是一个独根树（是不是想到了并查集？）。
2.边集合(edges)：
对图中的每条边按照权值大小进行排序。（是不是想到了优先队列？）
好了，下面该如何操作呢？
首先：我们从edges中选出权值最小的一条边来作为生成树的一条边，然后将该边的两个顶点合并为一个新的树。
然后：我们继续从edges中选出次小的边作为生成树的第二条边，但是前提就是边的两个顶点一定是属于两个集合中，如果不是
则剔除该边继续选下一条次小边。
最后：经过反复操作，当我们发现n个顶点的图中生成树已经有n-1边的时候，此时生成树构建完毕。
从图中我们还是很清楚的看到Kruskal算法构建生成树的详细过程，同时我们也看到了”并查集“和“优先队列“这两个神器
来加速我们的生成树构建。
二：构建
1.Build方法
这里我灌的是一些测试数据，同时在矩阵构建完毕后，将顶点信息放入并查集，同时将边的信息放入优先队列，方便我们在
做生成树的时候秒杀。
1 #region 矩阵的构建 2 /// <summary> 3 /// 矩阵的构建 4 /// </summary> 5 public void Build() 6 { 7 //顶点数 8 graph.vertexsNum = 6; 9 10 //边数11 graph.edgesNum = 8;12 13 graph.vertexs = new int[graph.vertexsNum];14 15 graph.edges = new int[graph.vertexsNum, graph.vertexsNum];16 17 //构建二维数组18 for (int i = 0; i < graph.vertexsNum; i++)19 {20 //顶点21 graph.vertexs[i] = i;22 23 for (int j = 0; j < graph.vertexsNum; j++)24 {25 graph.edges[i, j] = int.MaxValue;26 }27 }28 29 graph.edges[0, 1] = graph.edges[1, 0] = 80;30 graph.edges[0, 3] = graph.edges[3, 0] = 100;31 graph.edges[0, 5] = graph.edges[5, 0] = 20;32 graph.edges[1, 2] = graph.edges[2, 1] = 90;33 graph.edges[2, 5] = graph.edges[5, 2] = 70;34 graph.edges[4, 5] = graph.edges[5, 4] = 40;35 graph.edges[3, 4] = graph.edges[4, 3] = 60;36 graph.edges[2, 3] = graph.edges[3, 2] = 10;37 38 //优先队列，存放树中的边39 queue = new PriorityQueue<Edge>();40 41 //并查集42 set = new DisjointSet<int>(graph.vertexs);43 44 //将对角线读入到优先队列45 for (int i = 0; i < graph.vertexsNum; i++)46 {47 for (int j = i; j < graph.vertexsNum; j++)48 {49 //说明该边有权重50 if (graph.edges[i, j] != int.MaxValue)51 {52 queue.Eequeue(new Edge()53 {54 startEdge = i,55 endEdge = j,56 weight = graph.edges[i, j]57 }, graph.edges[i, j]);58 }59 }60 }61 }62 #endregion
2：Kruskal算法
并查集，优先队列都有数据了，下面我们只要出队操作就行了，如果边的顶点不在一个集合中，我们将其收集作为最小生成树的一条边，
按着这样的方式，最终生成树构建完毕，怎么样，组合拳打的爽不爽？
1 #region Kruskal算法 2 /// <summary> 3 /// Kruskal算法 4 /// </summary> 5 public List<Edge> Kruskal() 6 { 7 //最后收集到的最小生成树的边 8 List<Edge> list = new List<Edge>(); 9 10 //循环队列11 while (queue.Count() > 0)12 {13 var edge = queue.Dequeue();14 15 //如果该两点是同一个集合，则剔除该集合16 if (set.IsSameSet(edge.t.startEdge, edge.t.endEdge))17 continue;18 19 list.Add(edge.t);20 21 //然后将startEdge 和 endEdge Union起来，表示一个集合22 set.Union(edge.t.startEdge, edge.t.endEdge);23 24 //如果n个节点有n-1边的时候，此时生成树已经构建完毕，提前退出25 if (list.Count == graph.vertexsNum - 1)26 break;27 }28 29 return list;30 }31 #endregion最后是总的代码：
View Code
View Code 1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Diagnostics; 6 using System.Threading; 7 using System.IO; 8 using System.Threading.Tasks; 9 10 namespace ConsoleApplication2 11 { 12 public class Program 13 { 14 public static void Main() 15 { 16 MatrixGraph graph = new MatrixGraph(); 17 18 graph.Build(); 19 20 var edges = graph.Kruskal(); 21 22 foreach (var edge in edges) 23 { 24 Console.WriteLine("({0},{1})({2})", edge.startEdge, edge.endEdge, edge.weight); 25 } 26 27 Console.Read(); 28 } 29 } 30 31 #region 定义矩阵节点 32 /// <summary> 33 /// 定义矩阵节点 34 /// </summary> 35 public class MatrixGraph 36 { 37 Graph graph = new Graph(); 38 39 PriorityQueue<Edge> queue; 40 41 DisjointSet<int> set; 42 43 public class Graph 44 { 45 /// <summary> 46 /// 顶点信息 47 /// </summary> 48 public int[] vertexs; 49 50 /// <summary> 51 /// 边的条数 52 /// </summary> 53 public int[,] edges; 54 55 /// <summary> 56 /// 顶点个数 57 /// </summary> 58 public int vertexsNum; 59 60 /// <summary> 61 /// 边的个数 62 /// </summary> 63 public int edgesNum; 64 } 65 66 #region 矩阵的构建 67 /// <summary> 68 /// 矩阵的构建 69 /// </summary> 70 public void Build() 71 { 72 //顶点数 73 graph.vertexsNum = 6; 74 75 //边数 76 graph.edgesNum = 8; 77 78 graph.vertexs = new int[graph.vertexsNum]; 79 80 graph.edges = new int[graph.vertexsNum, graph.vertexsNum]; 81 82 //构建二维数组 83 for (int i = 0; i < graph.vertexsNum; i++) 84 { 85 //顶点 86 graph.vertexs[i] = i; 87 88 for (int j = 0; j < graph.vertexsNum; j++) 89 { 90 graph.edges[i, j] = int.MaxValue; 91 } 92 } 93 94 graph.edges[0, 1] = graph.edges[1, 0] = 80; 95 graph.edges[0, 3] = graph.edges[3, 0] = 100; 96 graph.edges[0, 5] = graph.edges[5, 0] = 20; 97 graph.edges[1, 2] = graph.edges[2, 1] = 90; 98 graph.edges[2, 5] = graph.edges[5, 2] = 70; 99 graph.edges[4, 5] = graph.edges[5, 4] = 40;100 graph.edges[3, 4] = graph.edges[4, 3] = 60;101 graph.edges[2, 3] = graph.edges[3, 2] = 10;102 103 //优先队列，存放树中的边104 queue = new PriorityQueue<Edge>();105 106 //并查集107 set = new DisjointSet<int>(graph.vertexs);108 109 //将对角线读入到优先队列110 for (int i = 0; i < graph.vertexsNum; i++)111 {112 for (int j = i; j < graph.vertexsNum; j++)113 {114 //说明该边有权重115 if (graph.edges[i, j] != int.MaxValue)116 {117 queue.Eequeue(new Edge()118 {119 startEdge = i,120 endEdge = j,121 weight = graph.edges[i, j]122 }, graph.edges[i, j]);123 }124 }125 }126 }127 #endregion128 129 #region 边的信息130 /// <summary>131 /// 边的信息132 /// </summary>133 public class Edge134 {135 //开始边136 public int startEdge;137 138 //结束边139 public int endEdge;140 141 //权重142 public int weight;143 }144 #endregion145 146 #region Kruskal算法147 /// <summary>148 /// Kruskal算法149 /// </summary>150 public List<Edge> Kruskal()151 {152 //最后收集到的最小生成树的边153 List<Edge> list = new List<Edge>();154 155 //循环队列156 while (queue.Count() > 0)157 {158 var edge = queue.Dequeue();159 160 //如果该两点是同一个集合，则剔除该集合161 if (set.IsSameSet(edge.t.startEdge, edge.t.endEdge))162 continue;163 164 list.Add(edge.t);165 166 //然后将startEdge 和 endEdge Union起来，表示一个集合167 set.Union(edge.t.startEdge, edge.t.endEdge);168 169 //如果n个节点有n-1边的时候，此时生成树已经构建完毕，提前退出170 if (list.Count == graph.vertexsNum - 1)171 break;172 }173 174 return list;175 }176 #endregion177 }178 #endregion179 }并查集：
View Code 1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 6 namespace ConsoleApplication2 7 { 8 /// <summary> 9 /// 并查集 10 /// </summary> 11 public class DisjointSet<T> where T : IComparable 12 { 13 #region 树节点 14 /// <summary> 15 /// 树节点 16 /// </summary> 17 public class Node 18 { 19 /// <summary> 20 /// 父节点 21 /// </summary> 22 public T parent; 23 24 /// <summary> 25 /// 节点的秩 26 /// </summary> 27 public int rank; 28 } 29 #endregion 30 31 Dictionary<T, Node> dic = new Dictionary<T, Node>(); 32 33 public DisjointSet(T[] c) 34 { 35 Init(c); 36 } 37 38 #region 做单一集合的初始化操作 39 /// <summary> 40 /// 做单一集合的初始化操作 41 /// </summary> 42 public void Init(T[] c) 43 { 44 //默认的不想交集合的父节点指向自己 45 for (int i = 0; i < c.Length; i++) 46 { 47 dic.Add(c[i], new Node() 48 { 49 parent = c[i], 50 rank = 0 51 }); 52 } 53 } 54 #endregion 55 56 #region 判断两元素是否属于同一个集合 57 /// <summary> 58 /// 判断两元素是否属于同一个集合 59 /// </summary> 60 /// <param name="root1"></param> 61 /// <param name="root2"></param> 62 /// <returns></returns> 63 public bool IsSameSet(T root1, T root2) 64 { 65 return Find(root1).CompareTo(Find(root2)) == 0; 66 } 67 #endregion 68 69 #region 查找x所属的集合 70 /// <summary> 71 /// 查找x所属的集合 72 /// </summary> 73 /// <param name="x"></param> 74 /// <returns></returns> 75 public T Find(T x) 76 { 77 //如果相等，则说明已经到根节点了，返回根节点元素 78 if (dic[x].parent.CompareTo(x) == 0) 79 return x; 80 81 //路径压缩(回溯的时候赋值，最终的值就是上面返回的"x"，也就是一条路径上全部被修改了) 82 return dic[x].parent = Find(dic[x].parent); 83 } 84 #endregion 85 86 #region 合并两个不相交集合 87 /// <summary> 88 /// 合并两个不相交集合 89 /// </summary> 90 /// <param name="root1"></param> 91 /// <param name="root2"></param> 92 /// <returns></returns> 93 public void Union(T root1, T root2) 94 { 95 T x1 = Find(root1); 96 T y1 = Find(root2); 97 98 //如果根节点相同则说明是同一个集合 99 if (x1.CompareTo(y1) == 0)100 return;101 102 //说明左集合的深度 < 右集合103 if (dic[x1].rank < dic[y1].rank)104 {105 //将左集合指向右集合106 dic[x1].parent = y1;107 }108 else109 {110 //如果 秩 相等，则将 y1 并入到 x1 中，并将x1++111 if (dic[x1].rank == dic[y1].rank)112 dic[x1].rank++;113 114 dic[y1].parent = x1;115 }116 }117 #endregion118 }119 }优先队列：
View Code 1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Diagnostics; 6 using System.Threading; 7 using System.IO; 8 9 namespace ConsoleApplication2 10 { 11 public class PriorityQueue<T> where T : class 12 { 13 /// <summary> 14 /// 定义一个数组来存放节点 15 /// </summary> 16 private List<HeapNode> nodeList = new List<HeapNode>(); 17 18 #region 堆节点定义 19 /// <summary> 20 /// 堆节点定义 21 /// </summary> 22 public class HeapNode 23 { 24 /// <summary> 25 /// 实体数据 26 /// </summary> 27 public T t { get; set; } 28 29 /// <summary> 30 /// 优先级别 1-10个级别 (优先级别递增) 31 /// </summary> 32 public int level { get; set; } 33 34 public HeapNode(T t, int level) 35 { 36 this.t = t; 37 this.level = level; 38 } 39 40 public HeapNode() { } 41 } 42 #endregion 43 44 #region 添加操作 45 /// <summary> 46 /// 添加操作 47 /// </summary> 48 public void Eequeue(T t, int level = 1) 49 { 50 //将当前节点追加到堆尾 51 nodeList.Add(new HeapNode(t, level)); 52 53 //如果只有一个节点，则不需要进行筛操作 54 if (nodeList.Count == 1) 55 return; 56 57 //获取最后一个非叶子节点 58 int parent = nodeList.Count / 2 - 1; 59 60 //堆调整 61 UpHeapAdjust(nodeList, parent); 62 } 63 #endregion 64 65 #region 对堆进行上滤操作，使得满足堆性质 66 /// <summary> 67 /// 对堆进行上滤操作，使得满足堆性质 68 /// </summary> 69 /// <param name="nodeList"></param> 70 /// <param name="index">非叶子节点的之后指针（这里要注意：我们 71 /// 的筛操作时针对非叶节点的） 72 /// </param> 73 public void UpHeapAdjust(List<HeapNode> nodeList, int parent) 74 { 75 while (parent >= 0) 76 { 77 //当前index节点的左孩子 78 var left = 2 * parent + 1; 79 80 //当前index节点的右孩子 81 var right = left + 1; 82 83 //parent子节点中最大的孩子节点，方便于parent进行比较 84 //默认为left节点 85 var min = left; 86 87 //判断当前节点是否有右孩子 88 if (right < nodeList.Count) 89 { 90 //判断parent要比较的最大子节点 91 min = nodeList[left].level < nodeList[right].level ? left : right; 92 } 93 94 //如果parent节点大于它的某个子节点的话，此时筛操作 95 if (nodeList[parent].level > nodeList[min].level) 96 { 97 //子节点和父节点进行交换操作 98 var temp = nodeList[parent]; 99 nodeList[parent] = nodeList[min];100 nodeList[min] = temp;101 102 //继续进行更上一层的过滤103 parent = (int)Math.Ceiling(parent / 2d) - 1;104 }105 else106 {107 break;108 }109 }110 }111 #endregion112 113 #region 优先队列的出队操作114 /// <summary>115 /// 优先队列的出队操作116 /// </summary>117 /// <returns></returns>118 public HeapNode Dequeue()119 {120 if (nodeList.Count == 0)121 return null;122 123 //出队列操作，弹出数据头元素124 var pop = nodeList[0];125 126 //用尾元素填充头元素127 nodeList[0] = nodeList[nodeList.Count - 1];128 129 //删除尾节点130 nodeList.RemoveAt(nodeList.Count - 1);131 132 //然后从根节点下滤堆133 DownHeapAdjust(nodeList, 0);134 135 return pop;136 }137 #endregion138 139 #region 对堆进行下滤操作，使得满足堆性质140 /// <summary>141 /// 对堆进行下滤操作，使得满足堆性质142 /// </summary>143 /// <param name="nodeList"></param>144 /// <param name="index">非叶子节点的之后指针（这里要注意：我们145 /// 的筛操作时针对非叶节点的）146 /// </param>147 public void DownHeapAdjust(List<HeapNode> nodeList, int parent)148 {149 while (2 * parent + 1 < nodeList.Count)150 {151 //当前index节点的左孩子152 var left = 2 * parent + 1;153 154 //当前index节点的右孩子155 var right = left + 1;156 157 //parent子节点中最大的孩子节点，方便于parent进行比较158 //默认为left节点159 var min = left;160 161 //判断当前节点是否有右孩子162 if (right < nodeList.Count)163 {164 //判断parent要比较的最大子节点165 min = nodeList[left].level < nodeList[right].level ? left : right;166 }167 168 //如果parent节点小于它的某个子节点的话，此时筛操作169 if (nodeList[parent].level > nodeList[min].level)170 {171 //子节点和父节点进行交换操作172 var temp = nodeList[parent];173 nodeList[parent] = nodeList[min];174 nodeList[min] = temp;175 176 //继续进行更下一层的过滤177 parent = min;178 }179 else180 {181 break;182 }183 }184 }185 #endregion186 187 #region 获取元素并下降到指定的level级别188 /// <summary>189 /// 获取元素并下降到指定的level级别190 /// </summary>191 /// <returns></returns>192 public HeapNode GetAndDownPriority(int level)193 {194 if (nodeList.Count == 0)195 return null;196 197 //获取头元素198 var pop = nodeList[0];199 200 //设置指定优先级（如果为 MinValue 则为 -- 操作）201 nodeList[0].level = level == int.MinValue ? --nodeList[0].level : level;202 203 //下滤堆204 DownHeapAdjust(nodeList, 0);205 206 return nodeList[0];207 }208 #endregion209 210 #region 获取元素并下降优先级211 /// <summary>212 /// 获取元素并下降优先级213 /// </summary>214 /// <returns></returns>215 public HeapNode GetAndDownPriority()216 {217 //下降一个优先级218 return GetAndDownPriority(int.MinValue);219 }220 #endregion221 222 #region 返回当前优先队列中的元素个数223 /// <summary>224 /// 返回当前优先队列中的元素个数225 /// </summary>226 /// <returns></returns>227 public int Count()228 {229 return nodeList.Count;230 }231 #endregion232 }233 }
经典算法题每日演练——第十六题 Kruskal算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。