一、什么是最小生成树
一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n－1条边。我们把构造连通网的最小代价生成树称为最小生成树。
例如下图中①、②、③都是左侧图的生成树，但③是构造连通网的最小代价，所以③是该图的最小生成树。
二、Prim算法
Prim算法的核心思想如下：
- ① 将图中所有顶点分为A、B两类，初始时所有顶点都在B类
- ② 选择任意一个顶点，将其放入A类
- ③ 从B类所有顶点出发，找一条连接A类某个顶点且权值最小的边。将这条边连接的B类中的顶点放入A类中。
- ④ 重复③步骤，直到所有B类中的顶点全部放入A类。
下面通过图来说明最小生成树的构建过程
首先，在初始时，所有顶点都在B类
选择顶点A放入A类中，然后寻找B类到A类权值最小的边。很显然是BA这条边
将顶点B放入A类中，然后继续寻找B类到A类权值最小的边。结果是AE
将顶点E放入A类中，继续寻找。结果是AC
将顶点C放入A类中，继续寻找。结果只有BD
将顶点D加入A类，构建结束。
原理很简单，直接上代码。这里的图采用邻接矩阵存储
// 边结构
struct Edge:IComparable<Edge>
{
public int from;
public int to;
public int weight;
public int CompareTo(Edge other)
{
return weight - other.weight;
}
}
private void Prim<T>(GraphByAdjacencyMatrix<T> graph)
{
var graphCount = graph.Count;
// 用来记录遍历过的顶点
bool[] nodes = new bool[graphCount];
// 用来记录当前遍历到的边
Edge[] edges = new Edge[graphCount];
// 将第一个顶点设置为已遍历
nodes[0] = true;
// 将第一个顶点对应的边加入集合
// 都从1开始遍历是因为n个顶点对应n-1条边
for (int i = 1; i < graphCount; i++)
{
edges[i] = new Edge {from = 0, to = i, weight = graph.Matrix[0, i]};
}
for (int i = 1; i < graphCount; i++)
{
// 找出权值最小的边
int min = Int32.MaxValue;
int minIndex = 0;
for (int j = 1; j < graphCount; j++)
{
if (!nodes[j] && edges[j].weight < min)
{
min = edges[j].weight;
minIndex = j;
}
}
// 将新的顶点加入已遍历集合
nodes[minIndex] = true;
// 打印边
Console.Write($"({edges[minIndex].from},{edges[minIndex].to}) ");
// 将新的顶点对应的边加入集合
// 忽略已经访问过的顶点、忽略比当前遍历的边更长的边
for (int j = 1; j < graphCount; j++)
{
if (!nodes[j] && edges[j].weight > graph.Matrix[minIndex, j])
{
edges[j] = new Edge {from = minIndex, to = j, weight = graph.Matrix[minIndex, j]};
}
}
}
}
Prim算法关注的是顶点，通过寻找各顶点上权值最小的边，逐步构建起最小生成树。Prim算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，n为顶点数。因此对于边数非常多的稠密图，Prim算法在性能上会更有优势。
三、Kruskal算法
与Prim算法关注顶点的思路不同，Kruskal算法关注点在于边。它的原理也很简单，就是先将所有的边按权值从小到大进行排序。然后遍历边集，只要遍历到的这条边不会与结果集中的边形成环，就将其加入结果集。
代码如下
private void Kruskal<T>(GraphByAdjacencyMatrix<T> graph)
{
// 自己实现的小根堆,用来对边排序
HeapList<Edge> edges = new HeapList<Edge>();
// 一维数组用来检验是否成环
int[] parent = new int[graph.Count];
// 将边加入小根堆
for (int i = 0; i < graph.Count; i++)
{
for (int j = i+1; j < graph.Count; j++)
{
if(graph.Matrix[i,j] == Int32.MaxValue) continue;
edges.Push(new Edge(){from = i,to=j,weight = graph.Matrix[i,j]});
}
}
for (int i = 0; i < graph.Count; i++)
{
// 弹出权值最小的边
var edge = edges.Pop();
int m = Find(parent, edge.from);
int n = Find(parent, edge.to);
// 如果n!=m,则未形成环路
if (n != m)
{
parent[m] = n;
// 打印边
Console.Write($"({edge.from},{edge.to})");
}
}
}
/// <summary>
/// 校验是否成环
/// </summary>
private int Find(int[] parent,int index)
{
while (parent[index] != 0)
{
index = parent[index];
}
return index;
}
这里的parent[]的作用可能有些难以理解。事实上它相当于一个并查集，用来检验是否成环。我们通过前面的例子来具体说明
首先进行校验的边是
(
1
,
2
)
(1,2)
(1,2)，此时parent[]中的元素都为0，因此返回的m = 1,n = 2，因为m != n，所以将parent[1] = 2。这步操作意味着将顶点B（下标为1）和C（下标为2）加入了集合，且集合的代表为C
接下来进行校验的边是
(
0
,
1
)
(0,1)
(0,1)。返回的m = 0,n = 2，所以将parent[0] = 2。即顶点A（下标为0）加入C这个集合
下一条边为
(
0
,
4
)
(0,4)
(0,4)，返回的m = 2,n = 4，所以将parent[2] = 4。即将C集合整个加入E所在的集合
接下来是
(
0
,
2
)
(0,2)
(0,2)，返回的m = 4,n = 4。此时n == m，意味着两个节点所在的集合都为E集合。也就是说这两个节点本身就是连通的，所以添加这条新的边会使生成树成环，需要舍弃。
接下来是
(
1
,
3
)
(1,3)
(1,3)，返回的m = 4,n = 3，所以将parent[4] = 3，即将E集合加入D所在的集合
生成树构建完成，退出循环。
当图的边数为
e
e
e时，Find()函数的时间复杂度为
l
o
g
e
loge
loge，外层循环的时间复杂度为
e
e
e。因此整个算法的时间复杂度为
e
l
o
g
e
eloge
eloge。Kruskal算法对于边数较少的稀疏图在性能上有很大优势。文章来源：https://www.toymoban.com/news/detail-451056.html
四、参考资料
[1].《大话数据结构》
[2]. http://c.biancheng.net/algorithm/prim.html文章来源地址https://www.toymoban.com/news/detail-451056.html
到了这里，关于最小生成树（Prim算法与Kruskal算法）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
