这篇我们看看第二种生成树的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
最后是总的代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
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 #endregion 128 129 #region 边的信息 130 /// <summary> 131 /// 边的信息 132 /// </summary> 133 public class Edge 134 { 135 //开始边 136 public int startEdge; 137 138 //结束边 139 public int endEdge; 140 141 //权重 142 public int weight; 143 } 144 #endregion 145 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 #endregion 177 } 178 #endregion 179 }
并查集:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
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 else 109 { 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 #endregion 118 } 119 }
优先队列:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
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 else 106 { 107 break; 108 } 109 } 110 } 111 #endregion 112 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 #endregion 138 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 else 180 { 181 break; 182 } 183 } 184 } 185 #endregion 186 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 #endregion 209 210 #region 获取元素并下降优先级 211 /// <summary> 212 /// 获取元素并下降优先级 213 /// </summary> 214 /// <returns></returns> 215 public HeapNode GetAndDownPriority() 216 { 217 //下降一个优先级 218 return GetAndDownPriority(int.MinValue); 219 } 220 #endregion 221 222 #region 返回当前优先队列中的元素个数 223 /// <summary> 224 /// 返回当前优先队列中的元素个数 225 /// </summary> 226 /// <returns></returns> 227 public int Count() 228 { 229 return nodeList.Count; 230 } 231 #endregion 232 } 233 }