如下图（左）所求，有若干个顶点需要全部连通，两个顶点之间的连通都有一定的权值（边值），如何连接可以使其边值求各达到最小？

这其实就是一个构造最小生成树的问题。

1 构造最小生成树的Kruskal算法

设G=（V，E）是无向连通带权图，V={1，2，…，n}，表示顶点，E表示边集；

设最小生成树T=（V，TE），该树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），基中V表示顶点，TE表示最小生成树的边集。Kruskal算法将这n个顶点看成是n个孤立的连通分支。它首先将所有的边按权值从小到大排序，然后只要 T 中选中的边数不到n−1，就做如下的贪心选择：

在边集E中选取权值最小的边（i，j），其中i、j表示边的顶点序号，如果将边（i，j）加入边集TE中不产生回路（圈），则将边（i，j）加入边集TE中，即用边（i，j）将这两个连通分支合并连接成一个连通分支；否则继续选择下一条最短边。把边（i，j）从集合E中删去。继续上面的贪心选择，直到T中所有顶点都在同一个连通分支上为止。此时，选取到的n−1条边恰好构成G的一棵最小生成树T。

那么，怎样判断加入某条边后图T会不会出现回路呢？

该算法对于手工计算十分方便，因为用肉眼可以很容易看到挑选哪些边能够避免构成回路（避圈法），但使用计算机程序来实现时，还需要一种机制来进行判断。Kruskal算法用了一个非常聪明的方法，就是运用集合避圈：如果所选择加入的边的起点和终点都在最小生成树T的集合中，那么就可以断定一定会形成回路（圈）。其实就是我们前面提到的“避圈法”：边的两个结点不能属于同一集合。

算法步骤：

① 初始化。将图G的边集E中的所有边按权值从小到大排序，边集TE={ }，把每个顶点都初始化为一个孤立的分支，即一个顶点对应一个集合。

② 在E中寻找权值最小的边（i，j）。

③ 如果顶点 i 和 j 位于两个不同连通分支，则将边（i，j）加入边集TE，并执行合并操作，将两个连通分支进行合并（序号→集合号、让集合号取相同值）。

④ 将边（i，j）从集合E中删去，即E=E−{（i，j）}。

⑤ 如果选取边数小于n−1，转②；否则，算法结束，生成最小生成树T。

2 完美图解

设G =（V，E）是无向连通带权图，如图98所示。

（1）初始化

将图G的边集E中的所有边按权值从小到大排序，如图2-99所示。

边集初始化为空集，TE={ }，把每个结点都初始化为一个孤立的分支，即一个顶点对应一个集合，集合号为该结点的序号，如图2-100所示↑。

（2）找最小

在E中寻找权值最小的边e1（2，7），边值为1。

（3）合并

结点2和结点7的集合号（顶点序号）不同，即属于两个不同连通分支，则将边（2，7）加入边集TE，执行合并操作（将两个连通分支所有结点合并为一个集合）；假设把小的集合号赋值给大的集合号，那么7号结点的集合号也改为2，如图2-101所示。

（4）找最小

在E中寻找权值最小的边e2（4，5），边值为3。

（5）合并

结点4和结点5集合号不同，即属于两个不同连通分支，则将边（4，5）加入边集TE，执行合并操作将两个连通分支所有结点合并为一个集合；假设我们把小的集合号赋值给大的集合号，那么5号结点的集合号也改为4，如图2-102所示↑。

（6）找最小

在E中寻找权值最小的边e3（3，7），边值为4。

（7）合并

结点3和结点7集合号不同，即属于两个不同连通分支，则将边（3，7）加入边集TE，执行合并操作将两个连通分支所有结点合并为一个集合；假设我们把小的集合号赋值给大的集合号，那么3号结点的集合号也改为2，如图2-103所示。

（8）找最小

在E中寻找权值最小的边e4（4，7），边值为9。

（9）合并

结点4和结点7集合号不同，即属于两个不同连通分支，则将边（4，7）加入边集TE，执行合并操作将两个连通分支所有结点合并为一个集合；假设我们把小的集合号赋值给大的集合号，那么4、5号结点的集合号都改为2，如图2-104所示↑。

（10）找最小

在E中寻找权值最小的边e5（3，4），边值为15。

（11）合并

结点3和结点4集合号相同，属于同一连通分支，不能选择，否则会形成回路。

（12）找最小

在E中寻找权值最小的边e6（5，7），边值为16。

（13）合并

结点5和结点7集合号相同，属于同一连通分支，不能选择，否则会形成回路。

（14）找最小

在E中寻找权值最小的边e7（5，6），边值为17。

（15）合并

结点5和结点6集合号不同，即属于两个不同连通分支，则将边（5，6）加入边集TE，执行合并操作将两个连通分支所有结点合并为一个集合；假设我们把小的集合号赋值给大的集合号，那么6号结点的集合号都改为2，如图2-105所示。

（16）找最小

在E中寻找权值最小的边e8（2，3），边值为20。

（17）合并

结点2和结点3集合号相同，属于同一连通分支，不能选择，否则会形成回路。

（18）找最小

在E中寻找权值最小的边e9（1，2），边值为23。

（19）合并

结点1和结点2集合号不同，即属于两个不同连通分支，则将边（1，2）加入边集TE，执行合并操作将两个连通分支所有结点合并为一个集合；假设我们把小的集合号赋值给大的集合号，那么2、3、4、5、6、7号结点的集合号都改为1，如图2-106所示↑。

（20）选中的各边和所有的顶点就是最小生成树，各边权值之和就是最小生成树的代价。

从上图可以看到，所有连通的图都只有一个相同的集合号，以此做为判断标准，避免构成回路。

3 代码

输入结点数n和边数m：7 12输入结点序号u、v和边值w：1 2 231 6 281 7 362 3 202 7 13 4 153 7 44 5 34 7 95 6 175 7 166 7 25

输出

输出排序后的结点序号u、v和边值w：2 - 7：14 - 5：33 - 7：44 - 7：93 - 4：155 - 7：165 - 6：172 - 3：201 - 2：236 - 7：251 - 6：281 - 7：36选中的各边的两个结点序号和其边值：2 - 7：14 - 5：33 - 7：44 - 7：95 - 6：171 - 2：23点连通成树后边值求和后的最小值：57

（1）时间复杂度：算法中，需要对边进行排序，若使用快速排序，执行次数为e*loge，算法的时间复杂度为O(e*loge)。而合并集合需要n−1次合并，每次为O(n)，合并集合的时间复杂度为O(n2)。

（2）空间复杂度：算法所需要的辅助空间包含集合号数组 nodeset[n]，则算法的空间复杂度是O(n)。

5 算法优化拓展

该算法合并集合的时间复杂度为O(n2)，我们可以用并查集的思想优化，使合并集合的时间复杂度降为O(e*logn)，优化后的程序做如下修改：

6 Kruskal算法与Prim算法的比较

（1）从算法的思想可以看出，如果图G中的边数较小时，可以采用Kruskal算法，因为Kruskal算法每次查找最短的边；边数较多可以用Prim算法，因为它是每次加一个结点。可见，Kruskal算法适用于稀疏图，而Prim算法适用于稠密图。

（2）从时间上讲，Prim算法的时间复杂度为O(n2)，Kruskal算法的时间复杂度为O(eloge)。

（3）从空间上讲，显然在Prim算法中，只需要很小的空间就可以完成算法，因为每一次都是从V−U集合出发进行扫描的，只扫描与当前结点集到U集合的最小边。但在Kruskal算法中，需要对所有的边进行排序，对于大型图而言，Kruskal算法需要占用比Prim算法大得多的空间。

附代码1

#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int N = 100;	// ① 数据结构int nodeset[N];				//集合号（顶点序号）数组int n, m;struct Edge {				//边的存储结构(两个顶点和一个权值)	int u;	int v;	int w;}e[N*N];	// ② 初始化void Init(int n){	for(int i = 1; i <= n; i++)		nodeset[i] = i;		//每个结点赋值一个集合号（顶点序号）}	// ③ 定义优先级，按边值进行升序排序bool comp(Edge x, Edge y){	return x.w < y.w;		}	// ④ 合并集合int Merge(int a, int b){ int p = nodeset[a];	//p为a结点的集合号（顶点序号） int q = nodeset[b];	//q为b结点的集合号（顶点序号） if(p==q) 		 return 0;			//集合号相同，什么也不做，返回 for(int i=1;i<=n;i++)	//检查所有结点，把集合号是q的全部改为p { if(nodeset[i]==q) nodeset[i] = p;	//a的集合号赋值给b集合号 } return 1;}int Kruskal(int n){	int ans = 0;	for(int i=0;i<m;i++)		if(Merge(e[i].u, e[i].v)) //如果执行了合并		{			ans += e[i].w;			n--;			cout<<e[i].u<<" - "<<e[i].v<<"："<<e[i].w<<endl;			if(n==1)				return ans;		}		return 0;}int main(){	cout <<"输入结点数n和边数m："<<endl;	cin >> n >> m;	Init(n);	cout <<"输入结点序号u、v和边值w："<<endl;	for(int i=0;i<m;i++)		cin >> e[i].u>> e[i].v >>e[i].w;	sort(e, e+m, comp);		//三个参数：待排序数组的首地址、尾地址，排序方式	cout <<"输出排序后的结点序号u、v和边值w："<<endl;	for(int j=0;j<m;j++)		cout<<e[j].u<<" - "<<e[j].v<<"："<<e[j].w<<endl;	cout<<"选中的各边的两个结点序号和其边值："<<endl;	int ans = Kruskal(n);	cout << "点连通成树后边值求和后的最小值：" << ans << endl;	system("pause");	return 0;}

附代码2

int Find(int x)				//找祖宗{	if(x != nodeset[x])		nodeset[x] = Find(nodeset[x]);//把当前结点到其祖宗路径上的所有结点的集合号改为祖宗集合号	return nodeset[x];		//返回其祖宗的集合号}int Merge(int a, int b)		//两结点合并集合号{	int p = Find(a);		//找a的集合号	int q = Find(b);		//找b的集合号	if(p==q) return 0;	if(p > q)		nodeset[p] = q;		//小的集合号赋值给大的集合号	else		nodeset[q] = p;	return 1;}

－End－