最小生成树

发表于 | 更新于 | 分类于

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 3010;
int a[N][N], d[N], n, m, ans;		//邻接矩阵a，最小生成树集合(T)里的点到其它(S)集合的点y (y <- S) d[y] = min(d[y], a[x][y]) 
	//	v[y] = 1表示点y在集合T中，否则在其它集合(S)中，按顺序每次枚举结点，加入T集合 
bool v[N]; 				//标记数组 
void prim()
{
	memset(d, 0x3f, sizeof(d));				//每个点到T集合的距离初始化为无穷大 
	for(int i = 1; i < n; i ++ )	//顺序枚举每个点，最后一个点时其它所有点已经被访问d[n]会被自身a[n][n]更新为0，所以不用要n节点 
	{
		int x = 0;		//记录最近节点下标，每次将第一个数纳入 
		for(int j = 1; j <= n; j ++ )	//记录离T集合最近的点 
			if(!v[j] && (x == 0 || d[j] < d[x]))	x = j;
		v[x] = 1;
		for(int y = 1; y <= n; y ++ )			//新加入的点与S集合里的点进行y (y 属于 S) 与 T集合最近距离的更新，方便下一次选，没有路径和为inf 
			if(!v[y])		d[y] = min(d[y], a[x][y]);
	}
}

int main()
{
	cin >> n >> m;			//n个节点，m条边  
	memset(a, 0x3f, sizeof(a));				//所有点距初始化为inf,即没有边相连 
	for(int i = 1; i <= n; i ++ )	a[i][i] = 0;	 //自己与自己没有边，距离为0; 
	for(int i = 1; i <= m; i ++ )	
	{
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z); 		//起点 终点 权值 
		a[x][y] = a[y][x] = min(z, a[x][y]);	//由于可能两点之间多边，又是无向图，连两条边，更新两点之间的最短距离 
	}	
	prim();
	for(int i = 2; i <= n; i ++ )		//由于d[1]为0， 所以即从d[2] + ···+ d[n]即可 
		ans += d[i]; 
	cout << ans << endl;
	return 0; 
}

kruskal算法

$(并查集 + 贪心)$

优点：复杂度较低 $O(mlogn)$，实现简单
缺点：边数较多，即稠密图中效率较低
思想 : 通过边进行贪心思想，优先选择边权值小的，并且这两个端点不能在同一个集合里
(即不连通，否则加上会出现环)

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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e5 + 20;			//边集 
const int M = 1e5 + 20; 		//顶点集 
struct rec{					//线段结构体, 起点，终点，权值 
	int x, y, z;
	bool operator < (const rec a) const{		//按小权值(e[i].z)排序 
		return z < a.z;
	}
}e[N];
int n, m, ans, fa[M];			//顶点(vertex)数, 边(edge)数，答案，父亲节点(并查集中使用) 
void init()			//并查集  		(并查集的初始化不能忘) 
{
	for(int i = 1; i <= n; i ++ )	fa[i] = i;
}

int get(int x)
{
	return fa[x] == x ? x : fa[x] = get(fa[x]);
}

void unite(int x, int y)
{
	fa[get(x)] = get(y); 
}

bool same(int x, int y)
{
	return get(x) == get(y);
}
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i ++ )
		scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].z);
	init();		//每个节点父亲节点初始化为自身(不能忘记初始化) 
	sort(e + 1, e + m + 1);			//按小到大排序 
	for(int i = 1; i <= m; i ++ )		//按边权值从小到大枚举 
	{
		if(same(e[i].x, e[i].y))	//两端点是否连通(父节点是否相同) 
			continue;
		unite(e[i].x, e[i].y);	//两端点不连通，合并两点，加上答案 
		ans += e[i].z;
	}
	cout << ans << endl;
	return 0;
}
0%