最小生成树

文章目录

1. 最小生成树

问题的描述

在日常生活中，我们会遇到这样的问题：在我们面前有几台电脑，需要我们使用网线将他们连起来，但是我们手头的网线长度有限，而且电脑很重不方便挪动，那么有什么办法可以利用最少的网线来将这些电脑都连起来呢？将这个问题抽象一下就得到了求最小生成树(Minimum spanning tree)这样的问题。

求解思路

由边出发的Kruskal算法

既然是要我们求出最小长度的连接边，那么我们可以对边进行排序，利用贪心的思想将那些权值最小的边依次添加进生成树中。当然这里的边也不是随便选择的，当权值最小边添加进生成树中，我们需要判断添加进这条边后，生成树是否构成环。如果能够成环，那么这条边不能添加到树中。最终当生成树的边数为节点数V-1时，最小生成树构建成功。

这种由边出发，逐步找出权值最小且加入后不使树成环的方法称为Kruskal算法。这里算法的证明我就略了，可以通过归纳和反证法来得到。

由点出发的Prim算法

上面我们提到了Kruskal算法，它是由边出发逐步构建生成树的，那么有没有方法是从点出发，来构建最小生成树的呢？答案是肯定的，这种由点出发的方法叫做Prim算法。

这个算法有点类似于用Dijkstra求最短路径的方法，先构建两个集合V1和V-V1，其中V1表示已经加入生成树的节点集合，V-V1当然表示还未被加入到生成树的节点集合。每次从V-V1中选出到V1集合最短距离的点加入到V1中，所谓到集合的最短距离，就是V-V1每个节点到V1每个节点的距离最小值。直到所有节点都被选进V1中。这个算法的证明我也略了，也可以通过反证法来证的。

Kruskal算法与Prim算法的比较

比较	Kruskal	Prim
思考出发点	从边出发贪心	从点出发贪心
复杂度	O(ElogE)	见下表
适合图	稀疏图	稠密图

伪代码

Kruskal算法

Kruskal(Graph G)
	MST: 储存结果的最小生成树集合
	Sort(G.edge); //先对图的边集进行排序
	for e in G.edge //遍历排好序的边集
		edgeCandidate = e;
		if (!makeLoop(e))//检查加入该边后是否会使MST中的边形成环
			MST.add(e);
	End
	output MST;
End

查阅网上资料，Kruskal可以用不想交集来查找是否成环。Kruskal的复杂度还是有排序来决定，所以复杂度为O(ElogE)。

Prim算法

Prim(Graph G)
	V: 储存结果的最小生成树的点集合
	D: V中点到未加入V的距离集合
	for v in G.vSet //遍历图中所有点
		pick minimum distance in D;
		add v to V;
		update D;
	End
	output V,D;
End

Prim算法思考方式有点像Dijkstra，所以算法复杂度的优化也可以参照Dijkstra

数据结构	复杂度
邻接矩阵	O(V^2)
二叉堆、邻接表	O(ElogV)
斐波那契堆	O(E+VlogV)

通过邻接矩阵图表示的简易实现中，找到所有最小权边共需O（V）的运行时间。使用简单的二叉堆与邻接表来表示的话，普里姆算法的运行时间则可缩减为O(ElogV)。如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为O(E+VlogV)。

举例说明

Kruskal

当然这里的MST可以有很多，比如在选取权值为2的边时，我们可以不选(2,4)，而选(4,5)，也能达到与4连通。