最小生成树——kruskal
发布日期:2021-06-29 05:37:35
浏览次数:4
分类:技术文章
本文共 1396 字,大约阅读时间需要 4 分钟。
Kruskal算法是基于贪心的算法,以边为基础进行扩展。首先我们把所有的边按照权值先从小到大排列,接着按照顺序选取每条边,如果这条边的两个端点不属于同一集合,那么就将它们合并,直到所有的点都属于同一个集合为止。合并的过程需要用到并查集(具体见)。
Kruskal的时间复杂度分析:
Kruskal算法每次要从都要从剩余的边中选取一个最小的边。通常我们要先对边按权值从小到大排序,这一步的时间复杂度为为O(|Elog|E|)。Kruskal算法的实现通常使用并查集,来快速判断两个顶点是否属于同一个集合。最坏的情况可能要枚举完所有的边,此时要循环|E|次,所以这一步的时间复杂度为O(|E|α(V)),其中α为Ackermann函数,其增长非常慢,我们可以视为常数。所以Kruskal算法的时间复杂度为O(|Elog|E|)。
代码:
#include#include #include #define INF 0xfffffff#define N 550using namespace std;struct Node{ int start, end, len; friend bool operator < (const Node& a, const Node& b){ return a.len < b.len; }};int father[N];int E, V;Node S[N];int GetFather(int cur){ // 并查集 获取父节点+ 路径压缩 return father[cur] == cur ? cur : father[cur] = GetFather(father[cur]);}bool Join(int a, int b){ // 判断a b两点是已连接 int fa = GetFather(a); int fb = GetFather(b); if(fa == fb){ return 1; } else{ father[fa] = fb; // 连接a b return 0; }}int Kruskal(){ int ans = 0; for(int i = 0; i < V; i++) // 边数添加完成后即可返回 if(!Join(S[i].start, S[i].end)) // 判断两点是否已经连接 ans += S[i].len; return ans;}int main(){ int loop; scanf("%d", &loop); while(loop --){ scanf("%d%d", &E, &V); for(int i = 1; i <= V; i ++){ // 初始化father数组 father[i] = i; } for(int i = 0; i < V; i ++) scanf("%d%d%d", &S[i].start, &S[i].end, &S[i].len); sort(S, S+V); int ans = Kruskal(); printf("%d\n", ans); } return 0;}
参考:
转载地址:https://blog.csdn.net/zhj_fly/article/details/74026126 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月19日 05时21分04秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
IIS 多站点HTTPS加密及自动http跳转到https
2019-04-29
NGINX重启HTTPS站点要Enter PEM pass phrase输入密码
2019-04-29
树莓派GPIO
2019-04-29
Android 热敏打印机打印二维码
2019-04-29
用vcgencmd获取树莓派硬件状态数据
2019-04-29
IIS 多域名多张证书配置
2019-04-29
树莓派LINUX 截屏
2019-04-29
树莓派Raspberry Pi的嵌入式QT平台
2019-04-29
apache https
2019-04-29
Debian Jessie安装支持HTML5音视频的Chromium浏览器听百度音乐
2019-04-29
nanopi2 启动信息
2019-04-29
POS打印机驱动大全
2019-04-29
phpstudy https
2019-04-29
centos apache 最新版HTTPS配置
2019-04-29
树莓派添加中文语音合成功能
2019-04-29
kangle https设置
2019-04-29
Linux下EasyPanel版本安装及升级
2019-04-29
raspberry pi(树莓派) + easycap d60 视频采集
2019-04-29
WebRTC
2019-04-29