再遇最小生成树（普里姆，普里姆+堆优化，克鲁斯卡尔）

本文主要是介绍再遇最小生成树（普里姆，普里姆+堆优化，克鲁斯卡尔），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

生成树概念：任何只由图G的边构成，并包含所有顶点的树称为G的生成树
最小生成树概念：最小生成树是其所有生成树中权重最小的生成树

算法区别

普里姆算法：普里姆算法贪的是点，适用于点少边多的稠密图，从不在点集合S的点中选出一个点，假设选出的点是j，我们让他与S内的某点距离最短，这样我们选出了一条生成树上的边，同时将点j加入S中，不断重复这个过程，直到所有点都加入点集合S。

克鲁斯卡尔算法：克鲁斯卡尔算法贪的是边，适用于点多边少的稀疏图，核心代码是用的是并查集思想，我们首先将边按照权值从小到大（利用结构体内嵌比较函数）排序后逐个判断，如果当前的边加入后不会产生环，那么就把当前边作为生成树的一条边，重复此过程，一共选取（V-1）条边，V为顶点数，最终得到的就是最小生成树

在编写普里姆算法的代码之前我们要知道普里姆算法需要哪些东西

首先要初始化图中两点之间距离无穷大
用closeset[maxn]记录不在S中的顶点在S中的最近邻接点
用lowcost[maxn]记录不在S中的顶点到S的最短距离，即到最近邻接点的权值
用vis[maxn]标记顶点是否被访问

时间复杂度分析：
T(n)=O(V^2)[邻接矩阵]——>稠密图
堆优化（小根堆）：T(n)=O(VlogV)+O(ElogV)=O(ElogV)
堆优化（斐波那契堆）：T(n)=O(E+VlogV)

下面通过题目来理解普里姆算法

题目描述
使用Prim算法求图的最小生成树(MST)
输入
每组数据分为两个部分，第一部分为图的点数n，和边数m,
第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。
输出
最小生成树，输出时按照边的两个端点的升序输出。（先看左端点，再看右端点，端点不换位置）
样例输入
3 3
0 1 10
0 2 15
1 2 50
样例输出
0 1 10
0 2 15

ps：1.这是一个最小生成树的模板题，要注意的就是得按边升序输出

普里姆算法是一种基于贪心思想求解加权无向图的最小生成树的算法
AC代码——普通版普里姆

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 10;
struct node
{int from, to, dis;bool operator<(const node x) const{if (from != x.from)return from < x.from;return to < x.to;}
} ans[maxn], w[maxn][maxn];
int pre[maxn], dis[maxn], vis[maxn], cnt, n;
//pre[i]表示dis的前一个点 dis[i]表示已经确定的点集到i的距离
void prim()
{memset(dis, inf, sizeof(dis)); //初始化距离memset(vis, 0, sizeof(vis));   //初始化标记node now, ne;dis[0] = 0, vis[0] = 1;     //把第一个点加到S中for (int i = 0; i < n; ++i) //初始化点集S中只有一个点0if (w[0][i].dis != inf)dis[i] = w[0][i].dis, pre[i] = 0; //先将与0相连的点的距离处理for (int i = 1; i < n; ++i){ //选剩下的n-1个点，每次循环找出一个到S距离最近的顶点int minn = inf, id = 0;//每一次循环计算所有没有使用的顶点到当前S的距离，得到在没有使用的顶点中到S的最短距离以及顶点号for (int j = 0; j < n; ++j){if (!vis[j] && dis[j] < minn){ //找到未确定的点到已确定点的距离最短的点idminn = dis[j];id = j;}}ans[++cnt] = w[pre[id]][id]; //答案vis[id] = 1;                 //已经使用过标记它for (int j = 0; j < n; ++j)  //松弛操作更新距离，因为新加入的点会影响S与其他点之间的距离{if (!vis[j] && dis[j] > w[id][j].dis){dis[j] = w[id][j].dis;pre[j] = id;}}}
}
int main()
{int m, a, b, c;node now;while (~scanf("%d %d", &n, &m)){cnt = 0;for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j)w[i][j].dis = inf; //初始距离设为无穷大表示不连通for (int i = 1; i <= m; ++i){ //无向图存边两次scanf("%d%d%d", &a, &b, &c);w[a][b].from = a, w[a][b].to = b, w[a][b].dis = c;w[b][a].from = a, w[b][a].to = b, w[b][a].dis = c;}prim();sort(ans + 1, ans + m);for (int i = 1; i < n; ++i)printf("%d %d %d\n", ans[i].from, ans[i].to, ans[i].dis);}return 0;
}

堆优化

堆是一种非常有趣的数据结构，他是一棵完全二叉树。有大根堆和小根堆两种（以下我们以小根堆为例介绍它）。
它支持插入和删除堆顶（也就是树根）的操作，它也始终满足一个性质——父亲节点的值小于等于其所有子孙，那么显而易见的，整棵树中的根节点的值就是最小的。
那么我们怎么在插入一个数的时候和删除堆顶（根）的时候维持其小根堆的性质呢？
当我们插入一个数的时候，就先将其放在堆的最后一个元素的后面，然后将他与他的父亲进行比较，如果他比他的父亲小，说明不满住小根堆性质，就将其与其父亲交换，交换之后重复这个操作，直到这个数到达它该到的位置。
当我们删除堆顶的时候，可以将最后一个数临时的补到堆顶位置，然后判断他是否可以放在堆顶——即是否是小于其两个儿子，如果不是说明它应该往下交换，将其和两个儿子中的小的那个交换，交换之后继续和他的儿子进行判断和交换，一直到交换到合适的位置。
这样就可以保证一直都是小根堆啦！

在这里插入图片描述
我们可以用c++STL里面的优先队列来定义，但是它默认是大根堆，所以有需要的话我们要手写小根堆

普里姆+堆优化代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 10;
struct node
{int a, b, v;bool operator<(const node x) const{if (a != x.a)return a < x.a;return b < x.b;}
} ans[maxn];
struct nod
{int from, to, dis, ju;bool operator<(const nod x) const{return dis > x.dis;}
};
vector<nod> w[maxn];
int dis[maxn], cnt;
void prim()
{memset(dis, inf, sizeof(dis));priority_queue<nod> pq;nod now, ne;dis[0] = 0;for (int i = 0; i < w[0].size(); ++i)pq.push(w[0][i]);while (!pq.empty()){now = pq.top(), pq.pop();if (now.ju)ans[++cnt].a = now.from, ans[cnt].b = now.to, ans[cnt].v = now.dis;elseans[++cnt].a = now.to, ans[cnt].b = now.from, ans[cnt].v = now.dis;for (int i = 0; i < w[now.to].size(); ++i){ne = w[now.to][i];if (dis[ne.to] > ne.dis){dis[ne.to] = ne.dis;pq.push(ne);}}}
}
int main()
{int n, m, from, to, v;nod now;while (~scanf("%d%d", &n, &m)){cnt = 0;for (int i = 1; i <= m; ++i){scanf("%d%d%d", &from, &to, &v);now.from = from, now.to = to, now.dis = v, now.ju = 1;w[from].push_back(now);now.from = to, now.to = from, now.ju = 0;w[to].push_back(now);}prim();sort(ans + 1, ans + m);for (int i = 1; i < n; ++i)printf("%d %d %d\n", ans[i].a, ans[i].b, ans[i].v);}return 0;
}

克鲁斯卡尔

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int pre[maxn];
int n, m, cnt, ans;
struct node
{int u, v, w;
} edge[maxn];
bool cmp(node a, node b)
{if (a.u != b.u)return a.u < b.u;elsereturn a.v < b.v;
}
bool cmp2(node a, node b)
{if (a.w != b.w)return a.w < b.w;
}
int find(int x)
{if (x != pre[x])pre[x] = find(pre[x]);return pre[x];
}
int main()
{while (~scanf("%d%d", &n, &m)){cnt = 0;for (int i = 1; i <= n; i++)pre[i] = i;for (int i = 1; i <= m; i++){int a, b, c;scanf("%d%d%d", &a, &b, &c);edge[i].u = a;edge[i].v = b;edge[i].w = c;}sort(edge + 1, edge + m + 1, cmp2);for (int i = 1; i <= m; i++){int u = find(edge[i].u), v = find(edge[i].v), w = edge[i].w;if (u != v){cnt++;pre[u] = v;ans += w;}}sort(edge + 1, edge + cnt + 1, cmp);for (int i = 1; i < n; ++i)printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].w);}return 0;
}