一、什么是最小生成树

一个连通图的生成树是一个极小的连通子图，它含有图中全部的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
{public int from;public int to;public int weight;public int CompareTo(Edge other){return weight - other.weight;}
}private void Prim(GraphByAdjacencyMatrix 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(n2)O(n^2)O(n2)，n为顶点数。因此对于边数非常多的稠密图，Prim算法在性能上会更有优势。

三、Kruskal算法

与Prim算法关注顶点的思路不同，Kruskal算法关注点在于边。它的原理也很简单，就是先将所有的边按权值从小到大进行排序。然后遍历边集，只要遍历到的这条边不会与结果集中的边形成环，就将其加入结果集。

代码如下

private void Kruskal(GraphByAdjacencyMatrix graph)
{// 自己实现的小根堆,用来对边排序HeapList edges = new HeapList();// 一维数组用来检验是否成环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})");}}
}/// 
/// 校验是否成环
/// 
private int Find(int[] parent,int index)
{while (parent[index] != 0){index = parent[index];}return index;
}

这里的parent[]的作用可能有些难以理解。事实上它相当于一个并查集，用来检验是否成环。我们通过前面的例子来具体说明