要么改变世界,要么适应世界
脚本 效率 教程 C 分享 工具 学习 命令行 HTML基础 CSS基础 JavaScript基础 Vue 动态规划 排序 分治 java 并查集 Shell 字符串 进程通信 单例模式 静态代理 动态代理 模板方法 观察者模式 高精度 阶乘 深度优先 递归 BFS 最大流 C语言课程设计 操作系课设 数据库 MySql Git SpringBoot 缓存 移位运算 与运算 或运算 位操作 快速排序 二分查找 LIS 单调递减栈 归并排序 链表 康托展开 映射 Jsp Cookie 质数 筛选法 凸包 最小生成树 贪心算法 最短路 多线程 KMP DFS 匈牙利算法 KM AC自动机 axios 框架 UI 算法 自动机 C++ 图论 ST表 模拟 总结 OpenCV 图像 Echarts 日历热力图 线性回归 多项式回归 泰勒展开 python NumPy 逻辑回归 MNIST Nuxt 前端 include漏洞 文件上传 SSRF 密码学 CBC fastjson RCE漏洞 pwn 栈溢出 数字签名 Solidity Web3.0 PoW 汇编 docker 容器 性能调优 仿真 信号 任务调度 并发 内存管理 GDB web 代理 红黑树 搜索 Django JNI 动态链接
该标签下的文章

利用并查集求最小生成树

2020-04-10 22:52:00
301
算法

## 什么是 Kruskal 算法? **Kruskal** 算法是求最小生成树的一种方法,有点类似于贪心算法,首先是按照边的权值从小到大进行排序,然后不断地将较小的边加入到过程解的集合,关键是要解决回路的问题,而利用并查集就可以很好地解决这个问题,即每次添加边之前,判断该边的两个顶点是否是处于相同的集合,相同就跳过,否则加入到过程解中,重复这个过程,知道最后只有一个集合,该集合即为所求。<!--more--> ...