当前位置: 首页 > news >正文

【图论】kruskal-最小生成树算法简析

克鲁斯卡尔(Kruskal)算法从另一途径求网的最小生成树。其基本思想是:假设连通网G=(V,E),令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),概述图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点分别在T中不同的连通分量上,则将此边加入到T中;否则,舍去此边而选择下一条代价最小的边。依此类推,直至T中所有顶点构成一个连通分量为止。——百度百科

比较抽象,\(kruskal\)算法利用直接存边的方法存图,对存储的边进行升序排序,从小到大加入我们的最小生成树中,并且结合并查集来检查是否会生成环,如果会生成环,那么我们就不把它加入到我们的最小生成树中,反之加入。

还是有点抽象,我们结合图来理解一下整个过程。
本代码根据洛谷P3366 【模板】最小生成树所写。传送锚点

image
此时,我们程序已经输入完成,并已经将边升序排序。
image
按照升序排序,我们应将最小的边先加入最小生成树中,显然,此时没有环生成,所以我们这两条边都可以添加。
image
现在我们要加入第二小的边,也没有环出现,可以添加。
image
现在我们要加入第三小的边,显然,有一条边(灰色标注)与当前的树生成了环(黄色标注),所以我们不能将这条边加入到我们的最小生成树中。
image
(画到这突然发现有能画直线的工具qwq)两条\(weight=4\)的边加入也会生成边,所以我们都不加入。
所以我们此图的最小生成树就有了:
image

具体实现:

道理都懂了,代码如何实现呢(此处参考了这篇博客的写法)
首先,我们要直接存边,当然你可以分开存(可能会有点麻烦),这里我们使用一个结构体来保存每一条边的信息:

struct EDGE{ll w;ll pre, to;
} tree[maxn];

\(w\)为当前边的权值,\(pre\)是这条边的起始点,\(to\)是这条边的终点。
问题来了,我们如何用并查集判断当前边加入后是否会生成环呢?

并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。——百度百科

(不会并查集可以先去学一下)使用并查集,用\(f\)数组存每个点的父亲,我们可以将每条边起点的父亲设为终点f[find(tree[x].pre)] = find(tree[x].to);,这样,我们就将插入的这条边的起点终点都并入到了并查集中。

那么怎么判断呢?如果我们这条边的起点终点的祖先是同一个find(tree[i].pre) == find(tree[i].to),那么说明生成了环。
image
(红色代表已经加入并查集)例如这种情况,现在我们要加入\(5\)\(0\)这条边,这两个点既然已经加入了并查集,所以它们俩的祖先是相同的,显然符合find(tree[i].pre) == find(tree[i].to)这种情况,我们就直接跳过。
image
另一种情况,我们要加入\(5\)\(1\)这条边,\(5\)在并查集中,\(1\)不在并查集中,这俩显然没有相同祖先,可以加入。
剩下一种俩点都不在并查集内的情况就不再赘述了。

void build(ll x){ans += tree[x].w; //答案加上权值f[find(tree[x].pre)] = find(tree[x].to); //将起点终点连接(加入并查集)return ;
}
ll find(ll x){ //查找祖先return f[x] == x ? x : f[x] = find(f[x]); //路径压缩写法,会更快
}
for (ll i = 1;i <= m;i ++) {if (num == n - 1) break; //最小生成树的边数很显然是点数-1(没有环,两两相连),边数到了就没有必要继续了if (find(tree[i].pre) == find(tree[i].to)) continue;//如果会生成环,就不添加此边build(i); ++ num;//边数加1}

完整代码:

#include <iostream>
#include <algorithm>
using namespace std;
const ll maxn = 2e5 + 5;
struct EDGE{ll w;ll pre, to;
} tree[maxn];
ll ans, f[maxn], num=0;
bool cmp(EDGE a, EDGE b){return a.w < b.w;
}
ll find(ll x){return f[x] == x ? x : f[x] = find(f[x]);
}
void build(ll x){ans += tree[x].w;f[find(tree[x].pre)] = find(tree[x].to);return ;
}
ll main(){ll n, m, x, y, z;cin >> n >> m;for (ll i = 1;i <= m;i ++) {cin >> x >> y >> z;tree[i].pre = x;tree[i].to = y;tree[i].w = z;}sort(tree + 1, tree + m + 1, cmp);for (ll i = 1;i <= n;i ++)f[i] = i;for (ll i = 1;i <= m;i ++) {if (num == n - 1) break;if (find(tree[i].pre) == find(tree[i].to)) continue;build(i); ++ num;}if (num != n - 1){cout << "orz";return 0;}cout << ans;return 0;
}

\(AC\)通过洛谷P3366 【模板】最小生成树传送锚点
下面我们来看一道简单的例题:
洛谷P1195 口袋的天空传送锚点
image
读题发现,这道题要连成\(K\)个棉花糖,而且要让花费的代价最小,其实就是我们的最小生成树。
其实就是把图中的点用一颗最小生成树连接起来,但是最后的答案要去掉其中的几条边,使这棵树变成\(K\)块。
完整跑完一遍\(kruskal\)然后再去掉其中最大的几条边比较麻烦,还需要记录这棵树中存在的每一条边,然后从大往小删除(不能从图中的所有边里面从大往小删,根据我们上面的例子,图中最大的边是4,但是两条权值为4的边都不在树中,所以会出现错误,所以想要这样做必须要记录树中的边)
我们可以从另外一种角度想一想,我们想要分成\(K\)块,我们是不是需要删除\((K(块数)-1)\)条边啊,最小生成树里\(M(边数)=N(点数)-1\),所以我们最小生成树中总共有\(N-1-(K-1)=N-K\)条边,那么我们只需让\(kruskal\)在有\(N-K\)条边时停止,就能得到我们的最终答案。
代码:(可\(AC\)通过)

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 5;
struct EDGE{int w;int pre, to;
} len[maxn];
int ans, f[maxn], num=0, tw[maxn], tot=0;
bool cmp(EDGE a, EDGE b){return a.w < b.w;
}
int find(int x){return f[x] == x ? x : f[x] = find(f[x]);
}
void build(int x){ans += len[x].w;tw[tot ++] = len[x].w;f[find(len[x].pre)] = find(len[x].to);return ;
}
int main(){int n, m, T;cin >> n >> m >> T;if (T > n){cout << "No Answer";return 0;}for (int i = 1;i <= m;i ++) {int x, y, z;cin >> x >> y >> z;len[i].pre = x;len[i].to = y;len[i].w = z;}sort(len + 1, len + m + 1, cmp);for (int i = 1;i <= n;i ++) f[i] = i;for (int i = 1;i <= m;i ++) {if (num == n - T) break;if (find(len[i].pre) == find(len[i].to)) continue;build(i);++ num;}if (num != n - T){cout << "No Answer";return 0;}cout << ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=37382

相关文章:

  • 水贝培育钻项链生产厂家口碑榜:基于专业测评的技术、工艺及市场优势深度分析
  • win 11关闭工具栏溢出
  • 别再说我不懂Node流了
  • 深入解析:Python调用优云智算安装的ComfyUI服务器
  • 2025 智能/商超照明/灯具/灯光/源头厂家推荐榜:上海富明阳 5 星领跑,这些优质灯具成商超新选
  • 2025 年化粪池生产厂家最新推荐排行榜:预制 / 水泥 / 玻璃钢等多类型优质厂商权威甄选
  • 权威调研榜单:湿式静电除尘设备生产厂家TOP3榜单好评深度解析
  • NumPy-数组学习手册-全-
  • latex 插图图片代码
  • 一键配置 Web 前端开发环境(PowerShell 自动化脚本)
  • 设置模式(Leo)
  • 深入解析:C# .NetCore WebApi 性能改进 响应压缩
  • 利用客户端路径遍历实现CSRF攻击 - CSPT2CSRF技术解析
  • 卓越SAP实施,铸就企业数字核心——哲讯科技,您值得信赖的数字化转型伙伴
  • 2025年比较好的反弹插入门厂家最新推荐榜
  • 2025年口碑好的滚筒筛土机推荐生产厂家
  • 2025年评价高的全品类全屋五金厂家推荐及选择建议
  • 2025 年折弯机厂家最新推荐排行榜:聚焦数控 / 电液伺服 / 液压等机型,精选企业助您精准采购
  • 2025年耐用的木工除尘设备厂家最新推荐榜
  • 2025年可靠的直流温升试验机厂家推荐及选择建议
  • 2025年专业的密集型母线槽推荐生产厂家
  • 2025年耐用的五谷杂粮超微粉碎机,牧草超微粉碎机推荐生产厂家
  • 2025年耐用的湿式除尘器,文丘里湿式除尘器厂家TOP推荐榜
  • Edge设置黑夜模式
  • C# 界面美化实战:从基础控件到现代设计
  • 2025年诚信的混凝土水沟滑模机厂家推荐及选择指南
  • 2025年专业的煤炭化验设备最新TOP排名厂家
  • 2025年可靠的舟山平双造粒螺杆推荐TOP品牌企业
  • 2025年10月国内抗醇类泡沫灭火剂生产厂家全景解析报告,基于专业测评的技术、性能及市场优势深度分析
  • 2025年知名的开门式厨房拉篮厂家推荐及采购指南