最小生成树,指的属于该生成树的任意一个点,到生成树其他任意的点距离最短或权重最小或代价最小。

image.png

普利姆算法(Prim)

算法思想

  • 用dist维护距离最小生成树集合的最短距离,每次选择dist中,未在集合中且距离集合最短的点。然后,把这个点加入集合,用这个点更新其他点到集合的距离。整理的思想根dijkstra很像,唯一区别是dist数组的含义不同。

算法流程
image.png

模板题目

  • Prim算法求最小生成树
  • image.png
  • 题目分析: 最小生成树是 n 个点 n-1 条边构成。通过数据范围观察,应该是一个稠密图,使用朴素Prim
  • 解题代码:
    • 
      	#include <iostream>
      	#include <algorithm>
      	#include <cstring>
      	using namespace std;
      
      	const int N = 510, INF = 0x3f3f3f3f;
      	int g[N][N];
      	// 保存点到集合的最短距离
      	int dist[N];
      	// 用来维护生成树集合
      	bool st[N];
      	int n, m;
      
      	int prim() {
      		memset(dist, 0x3f, sizeof dist);
      		int res = 0;
      		for (int i = 0; i < n; ++ i) {
      			int t = -1;
      			for (int j = 1; j <= n; ++ j) 
      				if (!st[j] && (t == -1 || dist[t] > dist[j]))
      					t = j;
      
      			// 如果不是第一次选择,如果选择的点是INF,这说明该图并没有连通,就不存在最小生成树
      			if (i && dist[t] == INF) 
      				return INF;
      			// 加上边权
      			if (i) res += dist[t];
      			for (int j = 1; j <= n; ++ j)
      				dist[j] = min(dist[j], g[t][j]);
      			st[t] = true;
      		}
      
      		return res;
      	}
      
      	int main() {
      
      		memset(g, 0x3f, sizeof g);
      		cin >> n >> m;
      
      		for (int i = 0; i < m; ++ i) {
      			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)
      			puts("impossible");
      		else
      			cout << t << endl;
      		return 0;
      
      	}
      

堆优化版(略)

克鲁斯卡尔算法

算法思想

  • 将所有边按权重从小到大排序,然后遍历所有边,通过并查集来维护最小生成树。当遍历一条边,边的两端没在一个集合中,就将两点加如到集合中。维护一个cnt,判断边数是否未 n - 1条边,来确定最小生成树。每次选的边,都是两点间最短的边,局部最优解,可以推向全局最优。

模板题目

  • Kruskal算法求最小生成树
  • image.png
  • 解题思路:看数据范围,推出时一个稀疏矩阵,所以通过克鲁斯卡尔算法求最小生成树。
  • 解题代码:
    • 
      	#include <iostream>
      	#include <algorithm>
      	#include <cstring>
      	using namespace std;
      	const int N = 2e5 + 10, INF = 0x3f3f3f3f;
      
      	struct node {
      		int a, b, c;
      		bool operator < (const node& o) const {
      			return c < o.c;
      		}
      	}edges[N];
      
      	int n, m;
      	int p[N];
      
      	int find(int x) {
      		if (p[x] != x) p[x] = find(p[x]);
      		return p[x];
      	}
      
      	int kruskal() {
      		// 并查集初始化
      		for (int i = 1; i <= n; ++ i)
      			p[i] = i;
      
      		// 将边按权重从小到大排序
      		sort(edges, edges + m);
      
      		int res = 0, cnt = 0;
      		for (int i = 0; i < m; ++ i) {
      			int a = edges[i].a, b = edges[i].b, c = edges[i].c;
      			a = find(a);
      			b = find(b);
      			// 判断两点是否在一个集合
      			if (a != b) {
      				cnt ++;
      				res += c;
      				// 合并集合
      				p[a] = b;
      			}
      		}
      		// 如果 n 个点不能构成 n - 1 边,说明这个图本身就不连通,就没有最小生成树
      		if (cnt < n - 1)
      			return INF;
      		return res;
      	}
      
      	int main() {
      		cin >> n >> m;
      		for (int i = 0; i < m; ++ i) {
      			int a, b, c;
      			cin >> a >> b >> c;
      			edges[i] = {a,b,c};
      		}
      
      		int t = kruskal();
      		if (t == INF)
      			puts("impossible");
      		else
      			cout << t << endl;
      
      		return 0;
      
      
      	}