淘宝客api调用到网站,运城手机网站制作,wordpress好不好,怎样调试 wordpress这篇我们看看第二种生成树的 Kruskal 算法#xff0c;这个算法的魅力在于我们可以打一下算法和数据结构的组合拳#xff0c;很有意思的。
一、思想
若存在 M{0,1,2,3,4,5}这样 6 个节点#xff0c;我们知道 Prim 算法构建生成树是从”顶点”这个角度来思考的#xff0c;然…这篇我们看看第二种生成树的 Kruskal 算法这个算法的魅力在于我们可以打一下算法和数据结构的组合拳很有意思的。
一、思想
若存在 M{0,1,2,3,4,5}这样 6 个节点我们知道 Prim 算法构建生成树是从”顶点”这个角度来思考的然后采用“贪心思想”来一步步扩大化最后形成整体最优解而 Kruskal 算法有点意思它是站在”边“这个角度在思考的首先我有两个集合。
1.1、顶点集合(vertexs)
比如 M 集合中的每个元素都可以认为是一个独根树是不是想到了并查集。
1.2、边集合(edges)
对图中的每条边按照权值大小进行排序。是不是想到了优先队列 首先我们从 edges 中选出权值最小的一条边来作为生成树的一条边然后将该边的两个顶点合并为一个新的树。 然后我们继续从 edges 中选出次小的边作为生成树的第二条边但是前提就是边的两个顶点一定是属于两个集合中如果不是则剔除该边继续选下一条次小边。 最后经过反复操作当我们发现 n 个顶点的图中生成树已经有 n-1 边的时候此时生成树构建完毕。 从图中我们还是很清楚的看到 Kruskal 算法构建生成树的详细过程同时我们也看到了”并查集“和“优先队列“这两个神器来加速我们的生成树构建。
二、构建
2.1、Build 方法
这里我灌的是一些测试数据同时在矩阵构建完毕后将顶点信息放入并查集同时将边的信息放入优先队列方便我们在做生成树的时候秒杀。 #region 矩阵的构建/// summary/// 矩阵的构建/// /summarypublic void Build(){//顶点数graph.vertexsNum 6;//边数graph.edgesNum 8;graph.vertexs new int[graph.vertexsNum];graph.edges new int[graph.vertexsNum, graph.vertexsNum];//构建二维数组for (int i 0; i graph.vertexsNum; i){//顶点graph.vertexs[i] i;for (int j 0; j graph.vertexsNum; j){graph.edges[i, j] int.MaxValue;}}graph.edges[0, 1] graph.edges[1, 0] 80;graph.edges[0, 3] graph.edges[3, 0] 100;graph.edges[0, 5] graph.edges[5, 0] 20;graph.edges[1, 2] graph.edges[2, 1] 90;graph.edges[2, 5] graph.edges[5, 2] 70;graph.edges[4, 5] graph.edges[5, 4] 40;graph.edges[3, 4] graph.edges[4, 3] 60;graph.edges[2, 3] graph.edges[3, 2] 10;//优先队列存放树中的边queue new PriorityQueueEdge();//并查集set new DisjointSetint(graph.vertexs);//将对角线读入到优先队列for (int i 0; i graph.vertexsNum; i){for (int j i; j graph.vertexsNum; j){//说明该边有权重if (graph.edges[i, j] ! int.MaxValue){queue.Eequeue(new Edge(){startEdge i,endEdge j,weight graph.edges[i, j]}, graph.edges[i, j]);}}}}#endregion2.2、Kruskal 算法
并查集优先队列都有数据了下面我们只要出队操作就行了如果边的顶点不在一个集合中我们将其收集作为最小生成树的一条边按着这样的方式最终生成树构建完毕。 #region Kruskal算法/// summary/// Kruskal算法/// /summarypublic ListEdge Kruskal(){//最后收集到的最小生成树的边ListEdge list new ListEdge();//循环队列while (queue.Count() 0){var edge queue.Dequeue();//如果该两点是同一个集合则剔除该集合if (set.IsSameSet(edge.t.startEdge, edge.t.endEdge))continue;list.Add(edge.t);//然后将startEdge 和 endEdge Union起来表示一个集合set.Union(edge.t.startEdge, edge.t.endEdge);//如果n个节点有n-1边的时候此时生成树已经构建完毕提前退出if (list.Count graph.vertexsNum - 1)break;}return list;}#endregion最后是总的代码 using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Diagnostics;using System.Threading;using System.IO;using System.Threading.Tasks;namespace ConsoleApplication2{public class Program{public static void Main(){MatrixGraph graph new MatrixGraph();graph.Build();var edges graph.Kruskal();foreach (var edge in edges){Console.WriteLine(({0},{1})({2}), edge.startEdge, edge.endEdge, edge.weight);}Console.Read();}}#region 定义矩阵节点/// summary/// 定义矩阵节点/// /summarypublic class MatrixGraph{Graph graph new Graph();PriorityQueueEdge queue;DisjointSetint set;public class Graph{/// summary/// 顶点信息/// /summarypublic int[] vertexs;/// summary/// 边的条数/// /summarypublic int[,] edges;/// summary/// 顶点个数/// /summarypublic int vertexsNum;/// summary/// 边的个数/// /summarypublic int edgesNum;}#region 矩阵的构建/// summary/// 矩阵的构建/// /summarypublic void Build(){//顶点数graph.vertexsNum 6;//边数graph.edgesNum 8;graph.vertexs new int[graph.vertexsNum];graph.edges new int[graph.vertexsNum, graph.vertexsNum];//构建二维数组for (int i 0; i graph.vertexsNum; i){//顶点graph.vertexs[i] i;for (int j 0; j graph.vertexsNum; j){graph.edges[i, j] int.MaxValue;}}graph.edges[0, 1] graph.edges[1, 0] 80;graph.edges[0, 3] graph.edges[3, 0] 100;graph.edges[0, 5] graph.edges[5, 0] 20;graph.edges[1, 2] graph.edges[2, 1] 90;graph.edges[2, 5] graph.edges[5, 2] 70;graph.edges[4, 5] graph.edges[5, 4] 40;graph.edges[3, 4] graph.edges[4, 3] 60;graph.edges[2, 3] graph.edges[3, 2] 10;//优先队列存放树中的边queue new PriorityQueueEdge();//并查集set new DisjointSetint(graph.vertexs);//将对角线读入到优先队列for (int i 0; i graph.vertexsNum; i){for (int j i; j graph.vertexsNum; j){//说明该边有权重if (graph.edges[i, j] ! int.MaxValue){queue.Eequeue(new Edge(){startEdge i,endEdge j,weight graph.edges[i, j]}, graph.edges[i, j]);}}}}#endregion#region 边的信息/// summary/// 边的信息/// /summarypublic class Edge{//开始边public int startEdge;//结束边public int endEdge;//权重public int weight;}#endregion#region Kruskal算法/// summary/// Kruskal算法/// /summarypublic ListEdge Kruskal(){//最后收集到的最小生成树的边ListEdge list new ListEdge();//循环队列while (queue.Count() 0){var edge queue.Dequeue();//如果该两点是同一个集合则剔除该集合if (set.IsSameSet(edge.t.startEdge, edge.t.endEdge))continue;list.Add(edge.t);//然后将startEdge 和 endEdge Union起来表示一个集合set.Union(edge.t.startEdge, edge.t.endEdge);//如果n个节点有n-1边的时候此时生成树已经构建完毕提前退出if (list.Count graph.vertexsNum - 1)break;}return list;}#endregion}#endregion}并查集 using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace ConsoleApplication2{/// summary/// 并查集/// /summarypublic class DisjointSetT where T : IComparable{#region 树节点/// summary/// 树节点/// /summarypublic class Node{/// summary/// 父节点/// /summarypublic T parent;/// summary/// 节点的秩/// /summarypublic int rank;}#endregionDictionaryT, Node dic new DictionaryT, Node();public DisjointSet(T[] c){Init(c);}#region 做单一集合的初始化操作/// summary/// 做单一集合的初始化操作/// /summarypublic void Init(T[] c){//默认的不想交集合的父节点指向自己for (int i 0; i c.Length; i){dic.Add(c[i], new Node(){parent c[i],rank 0});}}#endregion#region 判断两元素是否属于同一个集合/// summary/// 判断两元素是否属于同一个集合/// /summary/// param nameroot1/param/// param nameroot2/param/// returns/returnspublic bool IsSameSet(T root1, T root2){return Find(root1).CompareTo(Find(root2)) 0;}#endregion#region 查找x所属的集合/// summary/// 查找x所属的集合/// /summary/// param namex/param/// returns/returnspublic T Find(T x){//如果相等则说明已经到根节点了返回根节点元素if (dic[x].parent.CompareTo(x) 0)return x;//路径压缩(回溯的时候赋值最终的值就是上面返回的x也就是一条路径上全部被修改了)return dic[x].parent Find(dic[x].parent);}#endregion#region 合并两个不相交集合/// summary/// 合并两个不相交集合/// /summary/// param nameroot1/param/// param nameroot2/param/// returns/returnspublic void Union(T root1, T root2){T x1 Find(root1);T y1 Find(root2);//如果根节点相同则说明是同一个集合if (x1.CompareTo(y1) 0)return;//说明左集合的深度 右集合if (dic[x1].rank dic[y1].rank){//将左集合指向右集合dic[x1].parent y1;}else{//如果 秩 相等则将 y1 并入到 x1 中并将x1if (dic[x1].rank dic[y1].rank)dic[x1].rank;dic[y1].parent x1;}}#endregion}}优先队列 using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Diagnostics;using System.Threading;using System.IO;namespace ConsoleApplication2{public class PriorityQueueT where T : class{/// summary/// 定义一个数组来存放节点/// /summaryprivate ListHeapNode nodeList new ListHeapNode();#region 堆节点定义/// summary/// 堆节点定义/// /summarypublic class HeapNode{/// summary/// 实体数据/// /summarypublic T t { get; set; }/// summary/// 优先级别 1-10个级别 (优先级别递增)/// /summarypublic int level { get; set; }public HeapNode(T t, int level){this.t t;this.level level;}public HeapNode() { }}#endregion#region 添加操作/// summary/// 添加操作/// /summarypublic void Eequeue(T t, int level 1){//将当前节点追加到堆尾nodeList.Add(new HeapNode(t, level));//如果只有一个节点则不需要进行筛操作if (nodeList.Count 1)return;//获取最后一个非叶子节点int parent nodeList.Count / 2 - 1;//堆调整UpHeapAdjust(nodeList, parent);}#endregion#region 对堆进行上滤操作使得满足堆性质/// summary/// 对堆进行上滤操作使得满足堆性质/// /summary/// param namenodeList/param/// param nameindex非叶子节点的之后指针这里要注意我们/// 的筛操作时针对非叶节点的/// /parampublic void UpHeapAdjust(ListHeapNode nodeList, int parent){while (parent 0){//当前index节点的左孩子var left 2 * parent 1;//当前index节点的右孩子var right left 1;//parent子节点中最大的孩子节点方便于parent进行比较//默认为left节点var min left;//判断当前节点是否有右孩子if (right nodeList.Count){//判断parent要比较的最大子节点min nodeList[left].level nodeList[right].level ? left : right;}//如果parent节点大于它的某个子节点的话此时筛操作if (nodeList[parent].level nodeList[min].level){//子节点和父节点进行交换操作var temp nodeList[parent];nodeList[parent] nodeList[min];nodeList[min] temp;//继续进行更上一层的过滤parent (int)Math.Ceiling(parent / 2d) - 1;}else{break;}}}#endregion#region 优先队列的出队操作/// summary/// 优先队列的出队操作/// /summary/// returns/returnspublic HeapNode Dequeue(){if (nodeList.Count 0)return null;//出队列操作弹出数据头元素var pop nodeList[0];//用尾元素填充头元素nodeList[0] nodeList[nodeList.Count - 1];//删除尾节点nodeList.RemoveAt(nodeList.Count - 1);//然后从根节点下滤堆DownHeapAdjust(nodeList, 0);return pop;}#endregion#region 对堆进行下滤操作使得满足堆性质/// summary/// 对堆进行下滤操作使得满足堆性质/// /summary/// param namenodeList/param/// param nameindex非叶子节点的之后指针这里要注意我们/// 的筛操作时针对非叶节点的/// /parampublic void DownHeapAdjust(ListHeapNode nodeList, int parent){while (2 * parent 1 nodeList.Count){//当前index节点的左孩子var left 2 * parent 1;//当前index节点的右孩子var right left 1;//parent子节点中最大的孩子节点方便于parent进行比较//默认为left节点var min left;//判断当前节点是否有右孩子if (right nodeList.Count){//判断parent要比较的最大子节点min nodeList[left].level nodeList[right].level ? left : right;}//如果parent节点小于它的某个子节点的话此时筛操作if (nodeList[parent].level nodeList[min].level){//子节点和父节点进行交换操作var temp nodeList[parent];nodeList[parent] nodeList[min];nodeList[min] temp;//继续进行更下一层的过滤parent min;}else{break;}}}#endregion#region 获取元素并下降到指定的level级别/// summary/// 获取元素并下降到指定的level级别/// /summary/// returns/returnspublic HeapNode GetAndDownPriority(int level){if (nodeList.Count 0)return null;//获取头元素var pop nodeList[0];//设置指定优先级如果为 MinValue 则为 -- 操作nodeList[0].level level int.MinValue ? --nodeList[0].level : level;//下滤堆DownHeapAdjust(nodeList, 0);return nodeList[0];}#endregion#region 获取元素并下降优先级/// summary/// 获取元素并下降优先级/// /summary/// returns/returnspublic HeapNode GetAndDownPriority(){//下降一个优先级return GetAndDownPriority(int.MinValue);}#endregion#region 返回当前优先队列中的元素个数/// summary/// 返回当前优先队列中的元素个数/// /summary/// returns/returnspublic int Count(){return nodeList.Count;}#endregion}}
