加载中...

第十六题 Kruskal算法

这篇我们看看第二种生成树的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

最后是总的代码： 

  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. }

并查集： 

  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. }

优先队列： 

  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. }

还没有评论.