ACM 最小生成树 Kruskal Prim 算法模板

定义：

求最小生成树，有两种算法。一种是 Prim算法 ，另一种是Kruskal算法。
你们可以先看下这个最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示 看了都说好 嘻嘻

先讲一种比较简单的————Kruskal算法
贪心+并查集

详细证明链接

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 200005;
int father[N];
int n, m;
struct Edge
{
	int a, b, v;
	bool operator< (const Edge &W) const
	{
		return v < W.v;
	}
}edge[N];

// 并查集——寻找当前集合的代表元素
int find(int x)
{
	if (father[x] != x) father[x] = find(father[x]);
	return father[x];
}

// 所有边存储在 Edge edges[M]; 
// 函数返回最小生成树中所有边的总长度
int Kruskal()
{
	int res = 0;
	// 初始化并查集代表元素
	for (int i = 1; i <= n; i++) father[i] = i;
	sort(edge, edge + m);
	for (int i = 0; i < m; i++)
	{
		int a = edge[i].a, b = edge[i].b;
		if (find(a) != find(b))
		{
			res += edge[i].v;
			father[find(a)] = find(b);
		}
	}
	return res;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> edge[i].a >> edge[i].b >> edge[i].v;
	}
	cout << Kruskal();
	//system("pause");
	return 0;
}

prim 算法
莽夫 暴力找边

#include <iostream>
#include <algorithm>
#include <limits.h>
#include <cstdio>

using namespace std;
const int N = 5010;
int g[N][N], m, n, d[N];
int vis[N];
int INF = INT_MAX;
int prim()
{
	int res = 0;
	int k = 0;
	for (int i = 1; i <= n; i++)
	{
		d[i] = INF;
	}
	d[1] = 0;
	for (int i = 1; i <= n; i++)
	{
		k++;
		int x = 0;
		for (int j = 1; j <= n; j++)
		{
			if (!vis[j] && (x == 0 || d[j] < d[x]))
				x = j;
		}
		if(x==0) continue;
		vis[x] = 1;
		res += d[x];
		//cout << "dx: " << d[x] << endl;
		//更新与当前集合(x)相连的边的最小值
		for (int j = 1; j <= n; j++)
			if (!vis[j])d[j] = min(d[j], g[x][j]);
	}
	if (k == n)
		return res;
	else
		return 0;
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			g[i][j] = INF;
	for (int i = 1; i <= n; i++) g[i][i] = 0;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		g[x][y] =min(g[x][y], z);
		g[y][x] = g[x][y];
	}
	int res = prim();
	if (res)
		cout << res;
	else
		cout << "orz";
	//system("pause");
	return 0;
}

最后

以上就是俭朴云朵为你收集整理的ACM 最小生成树 Kruskal Prim 算法模板的全部内容，希望文章能够帮你解决ACM 最小生成树 Kruskal Prim 算法模板所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。