与最小生成树的爱恨情仇

最小生成树(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,一部分归为点集VA的初始集合为{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 相关的坑点,在这里给大家整理一些,不完全。

  1. 认真读题,一定要区分是有向图还是无向图,如果是无向图的话,邻接表记得开双倍,不然会爆;

  2. 对于 n 个点,只需要 n - 1 条边就可以连出一个MST,如果跑完一个Kruskal 后发现 k != n - 1 ,就说明连不出一个 MST,有些题会这么考;

  3. 对于一些题,往往不会明确告诉你是无向图,这时需要结合生活经验,发挥语文阅读能力,加以判断,实在不行,就用Kruskal;~笑死了根本不用存边~

  4. 稍微上难度的题会把 MST 和二分答案结合起来考,这就需要大家灵活运用~一切随缘~

  5. 有些题喜欢只给你点的坐标,这时就需要先用欧几里得距离算点的距离再存图再跑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---------------------------------------------------------------------

上一篇:学习随记三十六——非递归实现伸展树


下一篇:2021团体程序设计天梯赛 L2-2 病毒溯源