最小生成树（Prim算法与Kruskal算法）

Bertha 。 2023-09-23 17:04 136阅读 0赞

## 一、什么是最小生成树 ##

一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n－1条边。我们把构造连通网的最小代价生成树称为最小生成树。

例如下图中①、②、③都是左侧图的生成树，但③是构造连通网的最小代价，所以③是该图的最小生成树。  
![e9ed7e061a243c7a206292c9385a597b.png][]

## 二、Prim算法 ##

Prim算法的核心思想如下：

*  ① 将图中所有顶点分为A、B两类，初始时所有顶点都在B类
 *  ② 选择任意一个顶点，将其放入A类
 *  ③ 从B类所有顶点出发，找一条连接A类某个顶点且权值最小的边。将这条边连接的B类中的顶点放入A类中。
 *  ④ 重复③步骤，直到所有B类中的顶点全部放入A类。

下面通过图来说明最小生成树的构建过程

首先，在初始时，所有顶点都在B类  
![b0c1394b78ae0dc0f98b90d4328d7054.png][]

选择顶点A放入A类中，然后寻找B类到A类权值最小的边。很显然是BA这条边  
![e752205af4c0f82ccce0f9b8a896ea95.png][]

将顶点B放入A类中，然后继续寻找B类到A类权值最小的边。结果是AE  
![16e0651d1ae48af79dc92bf47f0b4bed.png][]

将顶点E放入A类中，继续寻找。结果是AC  
![84e8f7dfb8e4988779e2a0058a14e0b6.png][]

将顶点C放入A类中，继续寻找。结果只有BD  
![e59b3c6d3cfec5ae431e4f5a081f4428.png][]

将顶点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算法关注点在于边。它的原理也很简单，就是先将所有的边按权值从小到大进行排序。然后遍历边集，只要遍历到的这条边不会与结果集中的边形成环，就将其加入结果集。  
![691fc1379051c244b5587b565d98d653.png][]

代码如下

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[]`的作用可能有些难以理解。事实上它相当于一个并查集，用来检验是否成环。我们通过前面的例子来具体说明  
![de19d1dc61827875dae700a296cdd50f.png][]

首先进行校验的边是 ( 1 , 2 ) (1,2) (1,2)，此时`parent[]`中的元素都为0，因此返回的`m = 1,n = 2`，因为`m != n`，所以将`parent[1] = 2`。这步操作意味着将顶点B（下标为1）和C（下标为2）加入了集合，且集合的代表为C  
![6d1fc4260315bde46c8c9c6970eb954a.png][]

接下来进行校验的边是 ( 0 , 1 ) (0,1) (0,1)。返回的`m = 0,n = 2`，所以将`parent[0] = 2`。即顶点A（下标为0）加入C这个集合  
![0df51d518c6550da6dd4e42ab0c650dc.png][]

下一条边为 ( 0 , 4 ) (0,4) (0,4)，返回的`m = 2,n = 4`，所以将`parent[2] = 4`。即将C集合整个加入E所在的集合  
![211a6c169f7588b1b032bfabcef2a71a.png][]

接下来是 ( 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所在的集合  
![439f6c7437ce16a1f02d5737a9f865e2.png][]

生成树构建完成，退出循环。

当图的边数为 e e e时，`Find()`函数的时间复杂度为 l o g e loge loge，外层循环的时间复杂度为 e e e。因此整个算法的时间复杂度为 e l o g e eloge eloge。Kruskal算法对于边数较少的稀疏图在性能上有很大优势。

## 四、参考资料 ##

\[1\].《大话数据结构》  
\[2\]. [http://c.biancheng.net/algorithm/prim.html][http_c.biancheng.net_algorithm_prim.html]

[e9ed7e061a243c7a206292c9385a597b.png]: https://img-blog.csdnimg.cn/img_convert/e9ed7e061a243c7a206292c9385a597b.png
[b0c1394b78ae0dc0f98b90d4328d7054.png]: https://img-blog.csdnimg.cn/img_convert/b0c1394b78ae0dc0f98b90d4328d7054.png
[e752205af4c0f82ccce0f9b8a896ea95.png]: https://img-blog.csdnimg.cn/img_convert/e752205af4c0f82ccce0f9b8a896ea95.png
[16e0651d1ae48af79dc92bf47f0b4bed.png]: https://img-blog.csdnimg.cn/img_convert/16e0651d1ae48af79dc92bf47f0b4bed.png
[84e8f7dfb8e4988779e2a0058a14e0b6.png]: https://img-blog.csdnimg.cn/img_convert/84e8f7dfb8e4988779e2a0058a14e0b6.png
[e59b3c6d3cfec5ae431e4f5a081f4428.png]: https://img-blog.csdnimg.cn/img_convert/e59b3c6d3cfec5ae431e4f5a081f4428.png
[691fc1379051c244b5587b565d98d653.png]: https://img-blog.csdnimg.cn/img_convert/691fc1379051c244b5587b565d98d653.png
[de19d1dc61827875dae700a296cdd50f.png]: https://img-blog.csdnimg.cn/img_convert/de19d1dc61827875dae700a296cdd50f.png
[6d1fc4260315bde46c8c9c6970eb954a.png]: https://img-blog.csdnimg.cn/img_convert/6d1fc4260315bde46c8c9c6970eb954a.png
[0df51d518c6550da6dd4e42ab0c650dc.png]: https://img-blog.csdnimg.cn/img_convert/0df51d518c6550da6dd4e42ab0c650dc.png
[211a6c169f7588b1b032bfabcef2a71a.png]: https://img-blog.csdnimg.cn/img_convert/211a6c169f7588b1b032bfabcef2a71a.png
[439f6c7437ce16a1f02d5737a9f865e2.png]: https://img-blog.csdnimg.cn/img_convert/439f6c7437ce16a1f02d5737a9f865e2.png
[http_c.biancheng.net_algorithm_prim.html]: http://c.biancheng.net/algorithm/prim.html