最小生成树(MST)

  • 原因

    回顾一下旧知识

  • 概况

    在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即),而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集(即)且为无循环图,使得的 w(T) 最小,则此 T 为 G 的最小生成树。

    $\omega(t)=\sum\limits_{(u,v)\in t}{\omega (u,v)}$

    最小生成树其实是最小权重生成树的简称

  • 思想

    最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出。

一、kruskal(克鲁斯卡尔)算法

1. 基本思想

基本思想是:假设连通网G = (V,E),令最小生成树的初始状态为只有 n 个顶点而无边的非连通图 T =( V , {} ),
图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边的顶点分别在T中不同的连通分量上,则将此边加入到T中
否则,舍去此边而选择下一条代价最小的边。依此类推,直至T中所有顶点构成一个连通分量为止

2. 时间复杂度

克鲁斯卡尔的时间复杂度主要由排序方法决定,而克鲁斯卡尔的排序方法只与网中边的条数有关,而与网中顶点的个数无关,
当使用时间复杂度为O(elog2e)的排序方法时,克鲁斯卡尔的时间复杂度即为O(log2e),
因此当网的顶点个数较多、而边的条数较少时,使用克鲁斯卡尔算法构造最小生成树效果较好

ps:记得配和并查集使用

二、prim(普里姆)算法

1. 算法介绍

1).输入:一个加权连通图,其中顶点集合为V,边集合为E;
2).初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {},为空;
3).重复下列操作,直到Vnew = V:
        a.在集合E中选取权值最小的边<u, v>,其中u为集合Vnew中的元素,而v不在Vnew集合当中,
                并且v∈V(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
        b.将v加入集合Vnew中,将<u, v>边加入集合Enew中;
4).输出:使用集合Vnew和Enew来描述所得到的最小生成树。

2. 时间复杂度

最小边、权的数据结构 时间复杂度(总计)
邻接矩阵、搜索 O(V^2)
二叉堆、邻接表 O((V + E) log(V)) = O(E log(V))
斐波那契堆、邻接表 O(E + V log(V))
通过邻接矩阵图表示的简易实现中,找到所有最小权边共需O(V)的运行时间。
使用简单的二叉堆与邻接表来表示的话,普里姆算法的运行时间则可缩减为O(ElogV),其中E为连通图的边数,V为顶点数。
如果使用较为复杂的斐波那契堆,则可将运行时间进一步缩短为O(E+VlogV),
         这在连通图足够密集时(当E满足Ω(VlogV)条件时),可较显著地提高运行速度。

(@百度百科

  • 题目

P3366 【模板】最小生成树

模板,致敬,我用的kruskal

#include <bits/stdc++.h>
using namespace std;
struct node{
	int x,y,len;
}a[200005];

int f[100005];
int cmp(node num1,node num2){
	return num1.len<num2.len;
}
int find(int x){
	if (x!=f[x])	f[x]=find(f[x]);
	return f[x];
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].len);
	}
	long long ans=0;
	sort(a+1,a+1+m,cmp);
	for (int i=1;i<=n;i++)	f[i]=i;
	for (int i=1;i<=m;i++){
		int x=find(a[i].x),y=find(a[i].y);
		if (x!=y){
			ans+=a[i].len;
			f[x]=y;
		}
	}
	printf("%d",ans);
}

P1991 无线通讯网

** 其中主要就是kruskal,注意排序顺序和找第几大的边 **

#include <bits/stdc++.h>
using namespace std;
int n,m;
int x[1005],y[1005];
int f[1005];
struct node{
	int l,r;
	double len;
}a[250005];
int h=0;
double ans;
bool cmp(node num1,node num2){
	return num1.len<num2.len;
}
int find (int x){
	if (x!=f[x]) f[x]=find(f[x]);
	return f[x];
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&x[i],&y[i]);
	}
	for (int i=1;i<=m;i++){
		for (int j=i+1;j<=m;j++){
			h++;
			a[h].l=i;
			a[h].r=j;
			a[h].len=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
		}
	}
	sort(a+1,a+1+h,cmp);
	for (int i=1;i<=m;i++){
		f[i]=i;
	}
	int tot=0;
	for (int i=1;i<=h;i++){
		int x=find(a[i].l),y=find(a[i].r);
		if (x!=y){
			++tot;
			ans=a[i].len;
			f[x]=y;
		}
		if (tot==m-n){
			printf("%.2lf",ans);
			break;
		}
	}
	return 0;
}
上一篇:最小生成树


下一篇:1584. Min Cost to Connect All Points