与最小生成树的爱恨情仇

2024-02-20 22:33:46

最小生成树（MST）

一、前言

我院子里有两棵树,一棵是最小生成树,另一棵还是最小生成树。
                                                       ————鲁迅

回想起来，距离我学完最小生成树直到今天已经过了很久了，期间做了不少有关的题，虽然依然无法A掉蓝题，但我觉得我在这个知识点上有了长足的进步......

关于最小生成树（MST）的算法主要有两种，一种是Prim算法，一种是Kruskal算法，两种算法的核心思想与实现方法并不相同，它们的适用范围也不完全相同。

二、算法：Prim

Prim算法的核心思想是“蓝白点思想”，即：蓝点已进树，白点在树外。

我们假设有一张图，其中有 n 个点，m 条边，假设我们从某个点 V0 开始，首先将此点标记为蓝色（一开始均为白色），然后在与 V0 相连的众多边中，找到最短的那条边，并把这条边的终点 V1 标记为蓝点，然后以 V1 为定点，重复上述步骤，直到找到一个 MST。

Prim算法过程: 定义集合A表示已加入最小生成树的节点，定义dist[]数组表示其它节点到集合A的最短距离。初始时，A为空，dist[]为无穷,dist[1] = 0。接下来每次添加到A的边都是使树的边尽可能小的边，这个过程一直进行到不存在连接生成树的边为止。算法描述如下： 1.将一个图分为两部分，一部分归为点集A，一部分归为点集V，A的初始集合为{V1}，V的初始集合为{ALL-V1}。

有一个很重要的结论，对于 n 个点，只需要 n - 1 条边就可以连出一个MST。

算法本身不难理解，一些更进一步的解释在代码中有。

#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define gc getchar
#define INF 0x3f3f3f3f
#define MAXN 200000+10  //个人比较喜欢这种大气磅礴的头 

using namespace std;

int n, m, ans, head[MAXN], cnt, dist[MAXN]; //n为点数，m为边数，ans=MST
 //dist为当前点到起点的最短距离 
bool vis[MAXN];  //雁过留痕 

inline int read(){  //常规快读 
	ri x=0,f=1;char ch=gc();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc();}
	return x*f;
} 

struct Node{
	int st, to, next, w;
}e[MAXN<<1];

inline void add(int u, int v, int w){
	e[++cnt].st = u, e[cnt].to = v, e[cnt].w = w;
	e[cnt].next = head[u], head[u] = cnt;
} //邻接表存图 

void prim(){//Prim算法 
	for(ri i = 0; i <= n; i++) dist[i] = INF; //初始化 
	dist[1] = 0;  //V0即起点，起点到自己的dist为0 
	for(ri i = 1; i <= n; i++){
		int k = 0;
		for(ri j = 1; j <= n; j++)
			if(!vis[j] && dist[j] < dist[k]) k = j;
		vis[k] = 1;
		for(ri j = head[k]; j; j= e[j].next){  //经典松弛 
			if(!vis[e[j].to] && e[j].w < dist[e[j].to])
				dist[e[j].to] = e[j].w;
		}
	}
	for(ri j = 1; j <= n; j++){
		if(dist[j] == INF) return;
			else ans += dist[j]; 
	}
	return;
}

int main()
{
	n = read(), m = read();
	for(ri i = 1, u, v, w; i <= n; i++){
		u = read(), v = read(), w = read(); 
		add(u, v, w);   //无向图存两次 
		add(v, u, w);
	}
	
	prim();
	
	if(ans == 0) printf("Orz\n");
		else printf("%d\n", ans);
    return 0;  //好习惯 
}

显而易见，这个代码的时间复杂度是 n^2 ，不算特别优。

实际上有一个堆优化的prim，但由于和堆优化的Dikstra特别像，这里就不专门讲了，它的时间复杂度为nlogn, 大家自行体会。代码：link

三、算法：Kruskal

Kruskal算法的实质是贪心，在没有并查集之前，坦白讲，Kruskal算法很劣，但当它与并查集结合起来，可谓是威力无穷。

话不多说，很好理解，直接就上代码！~~（没学过并查集建议出门左转）~~

#include<bits/stdc++.h>
using namespace std;

int n, m, father[10005], ans, k;

struct node{
	int x, y, c;
}a[10005];

int find(int x){
	if (father[x]!=x){
		father[x] = find(father[x]);
	} else return father[x];
}

bool judge(int x, int y){
	if (find(x)==find(y)){
		return true;
	} else {
		return false;
	}
}

void unionn(int x, int y){
	father[find(x)] = find(y); 
}

bool cmp(node x, node y){
	return x.c<y.c;
}  

int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++){
		father[i] = i;
	}
	for (int i = 1; i <= m; i++){
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].c);
	}
	sort(a+1, a+1+m, cmp);
	for (int i = 1; i <= m; i++){
		if (!judge(a[i].x, a[i].y)){
			unionn(a[i].x, a[i].y);
			ans += a[i].c;
			k++;
		}
		if (k==n-1){
			break;
		}
	}
	printf("%d", ans);
	return 0;
}

唯一要强调的是，对于 n 个点，只需要 n - 1 条边就可以连出一个MST，这句话炒鸡炒鸡重要！！！

其实也有Kruskal的堆优化算法，但没多大意义，不优化已经够用了，好想好写。

四、算法选择

通过阅读代码，我们可以发现，Kruskal算法适用于稀疏图，即点数多于边数，而Prim算法适用于稠密图，即边数多于点数。

值得一提的是，理论上来说，优化后的Prim可以快不优化的Prim 100ms，但对于一些极端稠密的图，由于STL的常数较大，它的优势可能并不是那么明显，甚至会变慢。具体怎么选也要看个人喜好。

五、一些值得注意的知识

在做题的过程中，我们会发现一些和 MST 相关的坑点，在这里给大家整理一些，不完全。

认真读题，一定要区分是有向图还是无向图，如果是无向图的话，邻接表记得开双倍，不然会爆；
对于 n 个点，只需要 n - 1 条边就可以连出一个MST，如果跑完一个Kruskal 后发现 k != n - 1 ，就说明连不出一个 MST，有些题会这么考；
对于一些题，往往不会明确告诉你是无向图，这时需要结合生活经验，发挥语文阅读能力，加以判断，实在不行，就用Kruskal；~~~笑死了根本不用存边~~~
稍微上难度的题会把 MST 和二分答案结合起来考，这就需要大家灵活运用~~~一切随缘~~~

有些题喜欢只给你点的坐标，这时就需要先用欧几里得距离算点的距离再存图再跑Prim或者Kruskal，且一定要认真审题，注意保留小数。

inline void add(){
	for(int i = 1; i <= n; i++)
    	for(int j = i + 1; j <= n; j++){
        	e[++side].st = i, e[side].to = j;
        	e[side].w = sqrt((double)(po[i].x-po[j].x)*(po[i].x-po[j].x) + (double)(po[i].y-po[j].y)*(po[i].y-po[j].y));
    }
}

其他的等想起来再更......

六、后记

最小生成树就打算干到这里了，似乎NOIP也不喜欢考，接下来就该专攻动态规划啦~

各位，加油啊！！！
-----------------------------------------------------------------end---------------------------------------------------------------------

码农公寓