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

[图论]Kruskal

Kruskal

  • 本质:贪心,对边进行操作
  • 存储结构:边集数组。
  • 适用对象:可为负权图,可求最大生成树。
  • 核心思想:最短的边一定在最小生成树(MST)上,对最短的边进行贪心。
  • 算法流程:对全体边集 { E } \set{E} {E}由小到大排序。遍历所有边,每次添加使已选边集不成环的边,直到已选 V − 1 V-1 V1条边。可使用并查集判环,每次加边前先判断两点是否同属一个集合,每次加边时将两点合并到一个集合。
  • 复杂度: O ( E log ⁡ 2 E ) O(E\log_2E) O(Elog2E)

注:若无特殊说明,本文顶点与边编号均从0开始。

数据结构定义

using ll=long long;
ll n,m,s;//点数,边数,源点
struct edge{int u,v,w;
}e[m];
bool cmp(edge a,edge b){return a.w<b.w;
}
int s[n];
int Find(int x){if(s[x]!=x) s[x]=Find(s[x]);return s[x];
}
void init(){for(int i=0;i<n;i++) s[i]=i;
}

实现

int kruskal(){sort(e,e+m,cmp);init();int ans=0,cnt=0;for(int i=0;i<m;i++){if(cnt==n-1) break;int U=e[i].u,V=e[i].v,W=e[i].w;int u1=Find(U),u2=Find(V);if(u1==u2) continue;//成环,不选当前边else{ans+=W;s[u1]=u2;//合并到一个集合cnt++;}}if(cnt==n-1) return ans;return -1;
}

若求最大生成树,改为对边集 { E } \set{E} {E}由大到小排序即可。

http://www.xdnf.cn/news/2503.html

相关文章:

  • Windows快速切换屏幕/桌面
  • 如何自学机器学习?零基础到实战的完整路径
  • 超详细VMware虚拟机扩容磁盘容量-无坑版
  • 探索关系型数据库 MySQL
  • 驱动-自旋锁
  • opencv函数展示2
  • 4.17学习总结
  • 智能云图库-12-DDD重构
  • 【从零实现高并发内存池】thread cache、central cache 和 page cache 回收策略详解
  • DSO:牛津大学推出的物理一致性3D模型优化框架
  • Java与MySQL数据库连接的JDBC驱动配置教程
  • Java基础知识面试题(已整理Java面试宝典pdf版)
  • Operator 开发入门系列(一):Hello World
  • 什么是分库分表?
  • Linux中NFS服务设置
  • 《MySQL:MySQL表结构的基本操作》
  • 【天梯赛练习】L2-035 完全二叉树的层序遍历
  • 阿里云服务器的docker环境安装nacos--实践
  • 开源一体化白板工具Drawnix本地部署打造毫秒级响应的远程协作空间
  • 中介者模式(Mediator Pattern)
  • 目标检测概述
  • LeetCode 2176.统计数组中相等且可以被整除的数对:两层遍历模拟
  • Ubuntu 20.04.6编译安装COMFAST CF-AX90无线网卡驱动
  • Delphi Ini文件对UTF8支持不爽的极简替代方案
  • SpringAI+DeepSeek大模型应用开发——4 对话机器人
  • Qt界面卡住变慢的解决方法
  • 常用UI设计工具及平台概览
  • 【Pandas】pandas DataFrame xs
  • 关于视频的一些算法内容,不包含代码等
  • Java 中 Synchronized如何保证可见性