最小生成树

定义

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。

——百度百科

Kruskal

思路

用贪心的思想，把所有的边从短到长排序，从最短的边开始判断，如果连接的两个点不是已经联通的，那就把这条边连起来。如果已经联通，则忽略这条边。

用并查集维护所有的点，联通的点在同一集合，从而判断点是否联通。

模板

#define _CRTSECURE_NOWARNINGS
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
using namespace std;
#define MAXN 110

int n, m, f[MAXN];

struct EDGE
{
	int u, v, w;
} E[MAXN * MAXN];

bool cmp(EDGE x, EDGE y)	//边从小到大排序
{
	return x.w < y.w;
}

void Init(int x)	//并查集初始化
{
	for (int i = 1; i <= x; i++) f[i] = i;
}

int Find(int x)
{
	return x == f[x] ? x : f[x] = Find(f[x]);
}

void Kruskal(int n, int m)
{
	int res = 0;	// 存放结果
	int num = 0;	// 记录当前选择了多少条边
	Init(m);
	sort(E + 1, E + 1 + m, cmp);
	for (int i = 1; i <= m; i++)
	{
		int f1 = Find(E[i].u);	//  查询u顶点在哪个集合中
		int f2 = Find(E[i].v);	//  查询v顶点在哪个集合中
		if (f1 != f2)	//  如果不在同一个集合中
		{
			num++;	//  选中的边数 +1
			res += E[i].w;	//  答案加上这条边的权值
			f[f1] = f2;	//  将这两个点合并到一个集合中
		}
		if (num == n - 1)	// 如果已经找到了 n - 1条边，说明最小生成树已经构建完成了
			break;
	}
	if (num == n - 1) printf("%d\n", res);
	else  puts("Impossible\n");
}

int main() 
{
	//freopen("in.txt", "r", stdin);

	while (scanf("%d %d", &n, &m) != EOF)	//n 个点，m 条边
	{
		if (!m) break;
		for (int i = 1; i <= m; i++)
			scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
		Kruskal(n, m);
	}
    
	return 0;
    
}

复杂度 · $O(m \ log m)$

Prim

思路

1. 选用图中的任意一个顶点$V_{0}$，从 $v_{0}$ 开始生成最小生成树
2. 初始化 $d[v_{0}] \ = \ 0$，其他的点的距离值 $d[i] \ = \ INF$，其中 $d[i]$ 表示当前这棵小树到其他点的最小距离值
3. 经过 N 次如下步骤操作，最后得到一个含 N 各顶点，N - 1 条边的最小生成树
   1. 选择一个未标记的点 K，并且 $d[K]$ 的值是最小的
   2. 标记点 K 进入这棵小树
   3. 以 K 为中间点，更新这棵小树到未标记点的距离的最小值
4. 得到最小生成树 T

模板

#define _CRTSECURE_NOWARNINGS
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 110

int n, m, mp[MAXN][MAXN], vis[MAXN], d[MAXN];

void Initmap(int x)
{
	memset(mp, INF, sizeof(mp));
	for (int i = 1; i <= x; i++) mp[i][i] = 0;
}

void Prim(int n, int m)
{
	memset(vis, 0, sizeof(vis));
	int index = 1;	//当前加入到小树的顶点
	int res = 0;	//存放结果
	vis[index] = 1;
	for (int i = 1; i <= n; i++)	//更新这个点到其他点的距离  
		d[i] = mp[index][i];
	for (int i = 1; i < n; i++)	//执行 n - 1 次，找剩下的n - 1 个点
	{
		int minn = INF;
		for (int j = 1; j <= n; j++)	//找出未加入小树且 d 最小的点
		{
			if (!vis[j] && d[j] < minn)
			{
				minn = d[j];
				index = j;
			}
		}
		if (minn == INF)	//如果没有找到，说明不存在最小生成树
		{
			printf("Impossible\n");
			return;
		}
		res += minn;	//累加答案
		vis[index] = 1;	//将这个点加入最小生成树中
		for (int j = 1; j <= n; j++)	//更新这个点加入后，当前这棵小树到未加入的点的最近距离
		{
			if (!vis[j] && d[j] > mp[index][j]) d[j] = mp[index][j];
		}
	}
	printf("%d\n", res);
}
int main()
{
	//freopen("in.txt", "r", stdin);

	while (scanf("%d%d", &n, &m) != EOF)
	{
		if (!m) break;
		Initmap(n);
		for (int i = 1, u, v, w; i <= m; i++)
		{
			scanf("%d%d%d", &u, &v, &w);
			mp[v][u] = min(w, mp[u][v]);
			mp[u][v] = min(w, mp[u][v]);	// 消除重边的影响
		}
		Prim(n, m);
	}
    
	return 0;
    
}

复杂度 · $O(n^{2})$