概念：

最小生成树是一副连通加权无向图中一棵权值最小的生成树。

在现实生活中，经常要求在类似网络的复杂关系中，既要面面俱到（任意两个结点之间都可以访问到），又要使所用成本尽可能的小。最小生成树就是解决相关问题的。

一个连通图可能有多个不同的最小生成树，但是其权值之和一定相等。一棵最小生成树一定有N个顶点，N-1条边。通过对生成树关注的角度不同，有相应两种不同但同样常用的算法。

一、Prim算法：

prim算法是按每一步为一棵生长中的树添加一条边，该数最开始只有一个顶点，然后会添加v-1条边。

每次总是选择一条与生长中的树和图中与该树相连的部分所形成的具有最小权值的横切边添加到该生成树中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int G[MAXN][MAXN];//权值矩阵
int vis[MAXN];//记录访问
int lowc[MAXN];//记录与树连接的边的权重
memset(G,INF,sizeof(G));
memset(vis,false,sizeof(vis));
memset(lowc,INF,sizeof(lowc));


//标号0-n-1，返回最小生成树的权值，返回-1表示不连通
int Prim(int n){
	int ans = 0;
	
	//从0节点开始
	vis[0] = true;
	//首先更新与0结点直接相连的边的权值。
	for(int i = 1; i < n; i++) lowc[i] = G[0][i];
    //循环n-1次
	for(int i = 1; i < n; i++){
		int minc = INF;
		int p = -1;
		//找到与当前树相连并且权值最小的边。
		for(int j = 0; j < n; j++){
			if(!vis[j]&&minc > lowc[j]){
				minc = lowc[j];
				p = j;
			}
		}
		//不连通
		if(minc == INF) return -1;
		//更新树的权值
		ans += minc;
		vis[p] = true;
		//继续更新新树的最小权值数组。
		for(int j = 0; j < n; j++){
			if(!vis[j]&&lowc[j] > G[p][j])
				lowc[j] = G[p][j];
		}
	}
	return ans;
}

二、 Kruskal算法

算法流程：

  • 新建图G，G中拥有原图中相同的节点，但没有边。
  • 将原图中所有的边按权值从小到大排序
  • 从权值最小的边开始，如果这条边连接的两个结点与图G中不在同一个连通分量重，则添加这条边到图G中。
  • 重复3，直至图G中所有的结点都在同一个连通分量中。一共需要合并n-1次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
const int MAXN = 1010;//最大点数 
const int MAXM = 10000;//最大边数
 
int F[MAXN]; //并查集使用

//存储边的信息，起点，终点，权值
struct Edge{
	int u,v,w;
}edge[MAXM]; 
int tol = 0;//边数，加边前赋值为0

//加边函数
void addedge(int u,int v,int w){
	edge[tol].u = u;
	edge[tol].v = v;
	edge[tol++].w = w;
} 
//比较函数，排序用
bool cmp(Edge a,Edge b){
	return a.w < b.w;
} 
//查找元素所属集合。路径压缩版
int find(int x){
	return F[x] == -1 ? x : F[x] = find(F[x]);
}

//传入点数，返回最小生成树的权值，如果不连通返回-1
int Kruskal(int n){
	memset(F,-1,sizeof(F));
	//先对边排序
	sort(edge,edge+tol,cmp);
	int cnt = 0; //计算加入的边数。
	int ans = 0;
	//最多循环tol次
	for(int i = 0; i < tol; i++){
		int u = edge[i].u;
		int v = edge[i].v;
		int w = edge[i].w;
		int t1 = find(u);
		int t2 = find(v);
		//如果属于不同集合，合并
		if(t1 != t2){
			ans+= w;
			F[t1] = t2;
			cnt++;
		}
		//共需合并n-1次，已经完成，可提前结束
		if(cnt == n-1) break;
	} 
	if(cnt < n-1) return -1;//不连通
	return ans; 
}

对于稀疏图，选择Kruskal算法较优，而对于稠密图，Prim算法会更高效。

此外还有最大生成树，其实只要将图中的权值取反一下，就可以求得最大生成树，或者在kruskal算法，按从大到小排序之后再合并，得出来的也是最大生成树。