第十六题 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方法
这里我灌的是一些测试数据，同时在矩阵构建完毕后，将顶点信息放入并查集，同时将边的信息放入优先队列，方便我们在
做生成树的时候秒杀。
2：Kruskal算法
并查集，优先队列都有数据了，下面我们只要出队操作就行了，如果边的顶点不在一个集合中，我们将其收集作为最小生成树的一条边，
按着这样的方式，最终生成树构建完毕，怎么样，组合拳打的爽不爽？
最后是总的代码：
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>
/// 定义矩阵节点
/// </summary>
public class MatrixGraph
{
Graph graph = new Graph();
PriorityQueue<Edge> queue;
DisjointSet<int> set;
public class Graph
{
/// <summary>
/// 顶点信息
/// </summary>
public int[] vertexs;
/// <summary>
/// 边的条数
/// </summary>
public int[,] edges;
/// <summary>
/// 顶点个数
/// </summary>
public int vertexsNum;
/// <summary>
/// 边的个数
/// </summary>
public int edgesNum;
}
#region 矩阵的构建
/// <summary>
/// 矩阵的构建
/// </summary>
public 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 PriorityQueue<Edge>();
//并查集
set = new DisjointSet<int>(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>
/// 边的信息
/// </summary>
public class Edge
{
//开始边
public int startEdge;
//结束边
public int endEdge;
//权重
public int weight;
}
#endregion
#region Kruskal算法
/// <summary>
/// Kruskal算法
/// </summary>
public List<Edge> Kruskal()
{
//最后收集到的最小生成树的边
List<Edge> list = new List<Edge>();
//循环队列
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>
/// 并查集
/// </summary>
public class DisjointSet<T> where T : IComparable
{
#region 树节点
/// <summary>
/// 树节点
/// </summary>
public class Node
{
/// <summary>
/// 父节点
/// </summary>
public T parent;
/// <summary>
/// 节点的秩
/// </summary>
public int rank;
}
#endregion
Dictionary<T, Node> dic = new Dictionary<T, Node>();
public DisjointSet(T[] c)
{
Init(c);
}
#region 做单一集合的初始化操作
/// <summary>
/// 做单一集合的初始化操作
/// </summary>
public 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 name="root1"></param>
/// <param name="root2"></param>
/// <returns></returns>
public bool IsSameSet(T root1, T root2)
{
return Find(root1).CompareTo(Find(root2)) == 0;
}
#endregion
#region 查找x所属的集合
/// <summary>
/// 查找x所属的集合
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
public 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 name="root1"></param>
/// <param name="root2"></param>
/// <returns></returns>
public 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 中，并将x1++
if (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 PriorityQueue<T> where T : class
{
/// <summary>
/// 定义一个数组来存放节点
/// </summary>
private List<HeapNode> nodeList = new List<HeapNode>();
#region 堆节点定义
/// <summary>
/// 堆节点定义
/// </summary>
public class HeapNode
{
/// <summary>
/// 实体数据
/// </summary>
public T t { get; set; }
/// <summary>
/// 优先级别 1-10个级别 (优先级别递增)
/// </summary>
public int level { get; set; }
public HeapNode(T t, int level)
{
this.t = t;
this.level = level;
}
public HeapNode() { }
}
#endregion
#region 添加操作
/// <summary>
/// 添加操作
/// </summary>
public 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 name="nodeList"></param>
/// <param name="index">非叶子节点的之后指针（这里要注意：我们
/// 的筛操作时针对非叶节点的）
/// </param>
public void UpHeapAdjust(List<HeapNode> 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></returns>
public 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 name="nodeList"></param>
/// <param name="index">非叶子节点的之后指针（这里要注意：我们
/// 的筛操作时针对非叶节点的）
/// </param>
public void DownHeapAdjust(List<HeapNode> 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></returns>
public 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></returns>
public HeapNode GetAndDownPriority()
{
//下降一个优先级
return GetAndDownPriority(int.MinValue);
}
#endregion
#region 返回当前优先队列中的元素个数
/// <summary>
/// 返回当前优先队列中的元素个数
/// </summary>
/// <returns></returns>
public int Count()
{
return nodeList.Count;
}
#endregion
}
}
还没有评论.