Kruskal

原理

以边来求

排序实现

依次检查边是否处于联通块中

并查集 实现

以保证图连通且路径总权值最小

时间复杂度: O(M log M)

优化

if(k == n-1)
    break;

其中k为已选边数,n为点数,因为为连通的, 所以边数=点数-1

模版

#include<cstdio>
#include<algorithm>
using namespace std;
void merge(int, int);
int getf(int);
void add_edge(int, int, int);
int f[1002] = {}, edge_num = 0, n, m;
struct node{
	int u, v, w;
}edge[100002];
bool cmp(const node&, const node&);

int main()
{
	scanf("%d%d", &n, &m);
	int a, b, c;
	for(int i=1; i<=m; ++i)
	{
		scanf("%d%d%d", &a, &b, &c);
		add_edge(a, b, c);
	}
	sort(edge+1, edge+edge_num+1, cmp);
	int ans = -0x7ffffff, k = 0;
	int flag = 0;
	for(int i=1; i<=m; ++i)
	{
		int t1 = getf(edge[i].u), t2 = getf(edge[i].v);
		if(t1 != t2)
		{
			merge(t1, t2);
			if(ans < edge[i].w)
				ans = edge[i].w;
			++k;
		}
		if(k == n-1)
		{
			flag = 1;
			break;
		}
	}
	if(!flag)
		printf("-1");
	else
		printf("%d", ans);
	return 0;
}

bool cmp(const node &a, const node &b)
{
	return a.w < b.w;
}
void add_edge(int a, int b, int c)
{
	edge[++edge_num].u = a;
	edge[edge_num].v = b;
	edge[edge_num].w = c;
	return;
}
void merge(int x, int y)
{
	int t1 = getf(x), t2 = getf(y);
	if(t1 != t2)
		f[t2] = t1;
	return;
}
int getf(int x)
{
	if(f[x]!=x && f[x]!=0)
		return f[x] = getf(f[x]);
	return x;
}

代码题目 传送门


Prim

原理

类似Dijkstra松弛, 依次将白点变为蓝点

需要一个数组打标记,用k记录最小出边(初始化k = -1)

每次将dis数组更新为当前节点的所有出边的权值
找拥有最小权值的出边k
打标记book[k] = 1;
k节点重复第一步

求和dis数组,即为最短路径和
时间复杂度:O(N2N^2)

模版

#include<cstdio>
#include<cstring>
using namespace std;
int g[102][102];
int minn[102];
int book[102] = {};
int main()
{
	int n;
	scanf("%d", &n);
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=n; ++j)
			scanf("%d", &g[i][j]);
	memset(minn, 0x7f, sizeof(minn));
	minn[1] = 0;
	memset(book, 0, sizeof(book));
	for(int i=1; i<=n; ++i)
	{
		int k = 0;
		for(int j=1; j<=n; ++j)
			if(!book[j] && (minn[j]<minn[k]))
				k = j;
		book[k] = 1;
		for(int j=1; j<=n; ++j)
			if(!book[j] && (g[k][j]<minn[j]))
				minn[j] = g[k][j];
	}
	int ans = 0;
	for(int i=1; i<=n; ++i)
		ans += minn[i];
	printf("%d", ans);
	return 0;
}

代码题目传送门


选择

Prim适合稠密图Kruskal适合稀疏图

本蒟蒻小声BB:最小生成树其实不难 欢迎来我的博客