最小生成树算法大纲
最小生成树的基本概念
自由树和生成树
自由树（树）：
1、自由树就是一个无回路的连通图（没有确定根）
2、n个顶点就一定有n-1条边
生成树：
1、包含全部顶点
2、n-1条边全部在图中
图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。
最小生成树
如果图G是一个连通图，G上的一棵各边权值之和最小的带权生成树，称为G的最小生成树。
普利姆算法(prim)——模板题
通俗演示
例题描述
因为这是用来做分析的模板题，题目要求里就很直接明了的指出，要咱们求最小生成树的树边权重之和。现在就可以直接去观察数据范围，可以看出是稠密图，那么我们可爱的Prim算法就可以掏出来啦~
参考代码(C++版本)
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 510 , INF = 0x3f3f3f3f; int n,m; int g[N][N]; int dist[N]; bool st[N]; int prim() { //初始化距离数组 memset(dist,0x3f,sizeof dist); //res中存放最小生成树的树边权重之和 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; //如果不是第一个点以及距离最小的点距离是正无穷，说明当前距离最近的点，到集合的距离都是正无穷，即当前图不连通 if(i && dist[t] == INF) return INF; if(i) res += dist[t]; //用t去更新其他点 for(int j = 1; j <= n;j++) dist[j] = min(dist[j],g[t][j]);//注意这里是g[t][j],Dijkstra中是dist[t]+g[t][j] st[t] = true; } return res; } int main() { //输入 scanf("%d%d",&n,&m); //初始化邻接矩阵 memset(g,0x3f,sizeof g); //建图 while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); //因为是无向图，所以得建a 到 b 和 b 到 a的 g[a][b] = g[b][a] = min(g[a][b],c); } int t = prim(); if(t == INF ) puts("impossible"); else printf("%d\n",t); return 0; }
算法模板
Prim算法实现的流程图如下
Prim算法实现的代码描述：
int n; // n表示点数 int g[N][N]; // 邻接矩阵，存储所有边 int dist[N]; // 存储其他点到当前最小生成树的距离 bool st[N]; // 存储每个点是否已经在生成树中 // 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和 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; if (i && dist[t] == INF) return INF; if (i) res += dist[t]; st[t] = true; for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]); } return res; }
疑难杂症剖析
一、建图
g[a][b] = g[b][a] = min(g[a][b],c);
因为是无向图，所以需要建立从a 到 b的边 以及 从b 到 a的边
二、计算最小权值之和
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]);
将算法模板的代码实现看完的小伙伴可能发现，Prim算法和朴素版Dijkstra算法好像呀
相似，又不完全相似
Dijkstra算法中，dist数组维护的是1号点到当前点的距离
Prim算法中，dist数组维护的是当前点到已经存在的最小生成树集合的距离
因此
Dijkstra算法的更新是将t作为中介，将从1号点到j的距离dist[j] 和 1号点到t,再从t到j的距离dist[t]+g[t][j]作比较，找到最小的权值
Prim算法的更新则是，t是作为已经确实的最小生成树集合的代表
/
克鲁斯卡尔算法(Kruskal)——模板题
通俗演示
Kruskal算法在理解上是比Prim更舒服的
例题描述
参考代码(C++版本)
#include <iostream> #include <algorithm> using namespace std; const int N = 200010; int n,m; int p[N];//并查集 int cnt,res;//cnt存当前加入多少条边 ; res存放的是最小生成树中所有树边的权重之和 //kruskal算法可以不用邻接表存，只要把点和点到点的边存下来就好 //就不用使用复杂的数据结构，直接结构体搞了，只是要注意重载小于符号，让sort的时候可以根据权重来比较 struct Edge { int a,b,w; bool operator < (const Edge &W)const { return w < W.w; } }edges[N]; //并查集的find函数 int find(int x) { if(p[x] != x) p[x] = find(p[x]); return p[x]; } void kruskal() { //对存放的边按照权重排序 sort(edges,edges+m); //初始化并查集 for(int i = 1; i <= n;i++) p[i] = i; //从小到大枚举所以边 for(int i = 0; i < m; i++) { int a = edges[i].a, b = edges[i].b, w = edges[i].w; //找到a的祖宗结点 a = find(a),b = find(b); //如果a 和 b 不在一个连通块中 if(a != b) { //将a连通到b上 p[a] = b; res += w; cnt ++; } } } int main() { //输入 scanf("%d%d",&n,&m); //建图 for(int i = 0; i < m;i++) { int a,b,w; scanf("%d%d%d",&a,&b,&w); edges[i] = {a,b,w}; } kruskal(); //输出 ：输出一个整数，表示最小生成树的树边权重之和 //n个点，因为成最小生成树只能有n-1边 if(cnt < n-1) puts("impossible"); else printf("%d\n",res); return 0; }
算法模板
Kruskal算法的执行流程图如下;
Kruskal算法代码实现：
int n, m; // n是点数，m是边数 int p[N]; // 并查集的父节点数组 struct Edge { int a,b,w; }edges[N]; //自定义比较的方式，待会放置到sort函数中进行比较 bool cmp(Edge a,Edge b) { return a.w < b.w; } int find(int x) // 并查集核心操作 { if (p[x] != x) p[x] = find(p[x]); return p[x]; } int kruskal() { sort(edges, edges + m); for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集 int res = 0, cnt = 0; for (int i = 0; i < m; i ++ ) { int a = edges[i].a, b = edges[i].b, w = edges[i].w; a = find(a), b = find(b); if (a != b) // 如果两个连通块不连通，则将这两个连通块合并 { p[a] = b; res += w; cnt ++ ; } } if (cnt < n - 1) return INF; return res; }
疑难杂症剖析
一、存储边
Kruskal算法和Bellman-Ford算法挺相似的，都是随便大方的乖算法，只要能够获取到存储的信息就好。因此算法模板中可以使用最简单的结构体存储数据。
唯一需要注意的是，要重新制定比较的逻辑，让比较的逻辑是根据权重w来比较的。
二、并查集的使用
2.1、初始化并查集——让每个结点做自己的父结点
2.2、并查集的find函数的编写
