最小生成树

学习
字数统计: 1.6k   |   阅读时长≈ 7 分钟

最小生成树

0. 概述

  • 以下模板能使用的前提是：不存在负权环

1. 朴素Prim算法

时间复杂度：$O(n^2)$，适合稠密图，边数接近点数的平方

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

// 朴素Prim,和dijkstra非常相似
// 1.dist数组初始化为不可达
// 2.遍历每个点,找到集合外距离最近的点
// 3.用t更新其他点到集合的距离

const int N=5e2+10;
const int INF=1e9; // 无穷大

int n,m;
int g[N][N]; // 存储图
int dist[N]; // 存储各结点到生成树的距离
bool st[N]; // 访问状态
int pre[N]; // 节点的前驱节点

int prim() {
	// 初始化为不可达
	memset(dist,0x3f,sizeof dist);
	// 最终结果
	int res=0;
	dist[1]=0; // 从1号点开始生成
	// 对于每个点都遍历一遍
	for(int i=0;i<n;i++) {
		// t是距离点集最近的点
		int t=-1;
		// 从点1~n中去找t
		for(int j=1;j<=n;j++) {
			// 如果j未被访问并且t是第一次更新,并且从t到源点距离比从j到源点距离更近
			if(!st[j]&&(t==-1||dist[t]>dist[j]))
				t=j;
		}
		// 如果是孤立点,直接退出,无法构成最小生成树
		if(i && dist[t]==0x3f3f3f3f) {
			return INF;
		}
        // 先更新,再累加,防止把自环加进来
		// 状态更新
		st[t]=true;
		// 求和距离
		res+=dist[t];
		// 更新dist[j]
		for(int j=1;j<=n;j++)
			dist[j]=min(dist[j],g[t][j]);
		
		// 如果要输出边
//		for(int j=1;j<=n;j++) {
//			if(dist[j]>g[t][j]&&!st[j]) {
//				dist[j]=g[t][j];
//				pre[j]=t; // 距离变短,前驱变为t
//			}
//		}
		
	}
	return res;
}

void getPath() {
	for(int i=n;i>1;i--) {
		cout<<i<<' '<<pre[i]<<' '<<endl;
	}
}

int main() {
	cin>>n>>m;
	memset(g,0x3f,sizeof g);
	while(m--) {
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=g[b][a]=min(g[a][b],c); // 去重边
	}
	int t=prim();
	if(t==INF)
		cout<<"impossible";
	else
		cout<<t<<endl;
//	getPath();
	return 0;
}

2. Kruskal算法+并查集优化

时间复杂度：$O(mlog^n)$，适合稀疏图，以下模板能解决重边、自环、负权边
题目链接：P3366 【模板】最小生成树 - 洛谷

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=5e3+10; // 最大顶点数
const int M=2*(2e5+5); // 无向图

// 起点/终点/权值
struct Edge {
	int a;
	int b;
	int val;
}edges[M];

bool cmp(Edge a,Edge b) {
	return a.val<b.val;
}

int n,m;
int p[N]; // p[i]:顶点i的连通分量
int ans;

// 并查集查询连通分量,带路径压缩
int find(int x) {
	if(p[x]==x) return x;
	else return p[x]=find(p[x]);
}

bool kruskal() {
	int cnt=0; // 加入图的边数
	for(int i=1;i<=m;i++) {
		// 取出每条边中的信息
		int a=edges[i].a, b=edges[i].b, w=edges[i].val;
		
		// 如果a和b已经相连则跳过
		// 1.如果是自环->(3,3)=5
		// 2.如果是重边->(1,2)=3,(2,1)=5,此时取小边(因为排过序了)
		if(find(a)==find(b)) continue;
		
		// 输出这条边
//		cout<<a<<"--"<<b<<endl;
		
		// 选择这条边后的信息维护 
		p[find(a)]=find(b); // 连通两个并查集
		ans+=w; // 答案累加这条边的权值
		cnt++; // 边数+1
	}
	if(cnt==n-1) return true; // 联通
	return false;
}

int main() {
	cin>>n>>m;
	// 并查集初始化:连通分量为自身
	for(int i=1;i<=n;i++) {
		p[i]=i; 	
	}
	// 输入每条边
	for(int i=1;i<=m;i++) {
//		scanf("%d%d%d",&edges[i].a,&edges[i].b,&edges[i].val);
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		edges[i]={a,b,c};
	}
	sort(edges+1,edges+1+m,cmp);
	if(kruskal()) cout<<ans;
	else cout<<"orz";
	return 0;
}

3. Kruskal延申：对输出排序

将数组改成 $vector$，为结构体提供无参构造器和全参构造器 $m$，例题：信奥一本通 $p1348$，以下模板能解决重边、自环、负权边。
题目链接： 信息学奥赛一本通（C++版）

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e5+5; // 最大顶点数
const int M=2e5+5; // 最大边数

// 起点/终点/边权
struct Edge {
	int a;
	int b;
	ll val;
	// 构造器
	Edge(){}
	Edge(int aa,int bb,int cc) {
		a=aa;
		b=bb;
		val=cc;
	}
};

int n,m;
int fa[N]; // 记录父节点
ll ans;

vector<Edge> edges,tree; // 存储所有边和生成树的边

// 边权越小越靠前
bool cmp_edges(Edge a,Edge b) {
	return a.val<b.val;
}

// 对生成树的边二次排序,编号小的靠前
// 起始点相同,终点小的靠前;否则起始点小的靠前
bool cmp_trees(Edge x,Edge y) {
	if(x.a==y.a) return x.b<y.b;
	else return x.a<y.a;
}

// 查询根节点带路径压缩
int find(int x) {
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}

bool kruskal() {
	int cnt=0; // 已加入图的边
	for(Edge e:edges) {
		// 提取边的信息
		int a=e.a, b=e.b, w=e.val;
		int v1=find(a);
		int v2=find(b);
		// 若a,b已相连
		if(v1==v2) continue;
		// 选中这条边
		cout<<a<<' '<<b<<endl;
		ans+=w;
		fa[v1]=v2; // 联通并查集
		cnt++;
		tree.push_back(e); // 添加到生成树边集中
	}
	if(cnt==n-1) return true;
	return false;
}

int main() {
	// 优化输入输出
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	// 初始化并查集
	for(int i=1;i<=n;i++) {
		fa[i]=i;	
	}
	while(m--) {
		int a,b,c;
		cin>>a>>b>>c;
		// 强行让小的编号在前,大的编号在后
		if(a>b) swap(a,b);
		edges.push_back(Edge(a,b,c));
	}
	sort(edges.begin(),edges.end(),cmp_edges);
	if(kruskal()) cout<<ans<<endl;
	// 对生成树中的边再排序
	sort(tree.begin(),tree.end(),cmp_trees);
	for(auto e:tree) {
		cout<<e.a<<' '<<e.b<<' '<<e.val<<endl;
	}
	return 0;
}
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信