【模板】MST最小生成树（Prim算法、Krustra算法）

MST最小生成树问题

给一张n个点的图，从中选 n-1条边，使得所选边权和最小的情况下生成一个树。
解法核心：贪心

法一：Prim算法

1、核心思路： 点集拓展

2、核心操作：贪心（优先队列实现） + 判环（集合/标记 实现）

3、算法流程：

step1. 随机选取一个点不在集合内的点，并将该点连接的所有边加入优先队列，
step2. 选取优先队列的top（即集合当前所连接所有边中的最短边），将该边作为树的其中一个边，
step3. 将所连向的to_pos加入集合，如果该点已经在集合，则换下一条边，进行前述操作。
step4. 重复上述操作，直到所有点全部加入集合
注：推荐使用邻接矩阵。

4、复杂度分析：

O( N + logM) ⇒ 适用于密集图（边较多时）

5、 代码模板：

struct ss{//邻接表存图
	int to,nex,va;
	bool operator >const (ss b){return va<b.va;}
}edge[N];int head[N],ecnt;
priority_queue<ss> Q;
int prim(){
	vis[1]=true;int count=1,ans=0;//把第一个点放进去（也可以是任意一个）
	for(int i=head[1];i;i=edge[i].nex) Q.push(edge[i]);
	while(count<n && !Q.empty()){
		int to=Q.top().to;Q.pop();
		if(vis[to]) continue;
		count++;ans+=Q.top().va; vis[to]=true;//记录答案+集合标记
		for(int i=head[to];i;i=edge[i].nex) //放入边
		if(!vis[edge[i].to]) Q.push(edge[i]);//排序时间挺长的，能不入队就不入队
	}if(count<n) return -1;//图不连通，报错
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

法二：Krustra算法

1、核心思路： 选边法

2、核心操作：贪心（一次排序实现） + 判环（并查集实现）

3、算法流程：

step1. 将所有边排序
step2. 每次都选取最短的边，将该边作为树的边，
如果该边所连向的两个点 已经在同一并查集，则弃之不用
否则该边合法，选用该边，更新并查集
step4. 重复前述操作，直至n-1条边被选用，或直至所有边被遍历一遍

4、复杂度分析：

算法复杂度： O(m logm) ⇒ 适用于稀疏图（边较少时)

5、 代码模板：

struct ss{//邻接表存图
	int x,y,va;
}edge[N];int f[N];
bool cmp(ss a,ss b){return a.va<b.va;}
int fa(int x){//路径压缩并查集
	if(f[x]==x) return x;
	else return f[x]=fa(f[x]);
}
int krustra(){
	sort(edge+1,edge+m+1,cmp);int ans=0,count=0;
	for(i=1;i<=m;i++){
		int x=edge[i].x,y=edge[i].y;
		if(fa(x)==fa(y)) continue;//已经连通
		ans+=edge[i].va;//更新答案
		f[x]=fa(y);//更新连接
		count++;if(count==n-1) break;//剪枝
	}return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

注： prim算法如果要做非连通图的最小生成森林树，则需外面加一个循环，将所有点都视为初始放入节点。

---

ps.补一些基础模板，以便自己使用