最小生成树（prim和kruskal）
2024-09-02 15:27:39
最小生成树（prim和kruskal）
最小生成树的最优子结构性质
设一个最小生成树是T。如果选出一个T中的一条边，分裂成的两个树T1，T2依然是它们的点集组成的最小生成树。这可以用反证法来证。反着来推可以得出：如果有两个最小生成树T1，T2，将它们用它们之间的最短边连接起来，所得到的还是最小生成树。这个性质在关于（最小）生成树的状压dp里可以用。
prim算法
prim是在当前的最小生成树基础上，选择一条最短边作为新的最小生成树。将新加入的点看做一个最小生成树即可。用堆来加速的话，时间复杂度是\(O(mlogn)\)。缺点是空间占用大（因为堆）。由于prim算法需要知道当前点周围的边是什么，一般配合邻接表。
kruskal算法
kruskal算法和prim在思路上的唯一区别就是kruskal每次合并的是一整棵树，而不是一个点。如果用并查集，时间复杂度是\(O(mlogm)\)，优点是代码简单，不过基本上跑不过prim。如果是稠密图时间相差两倍左右，稀疏图则能差到五倍以上。kruskal并不需要每个点周围的边，并且用邻接表做反而麻烦，所以一般选用前向星。
最新文章
- Yii 2.x Behavior - 类图
- HTML5中lineCap端点样式遇到closePath()
- ServletContext图解
- 如何获取google可以访问的IP地址
- uva 10120
- OS X EL Capitan安装Cocoapods 报错ERROR
- 04747_Java语言程序设计（一）_第6章_图形界面设计（二）
- Python学习入门基础教程(learning Python)--6 Python下的list数据类型
- R语言学习 第八篇：常用的数据处理函数
- matlab 写文件
- lab-kvm
- Hadoop小知识点总结1
- Java并发编程--总结
- VIM vim/vi的文件内、跨文件复制粘贴操作、替换操作
- zabbix 3.2源码安装
- springSecurity自定义认证配置
- python处理图片验证码
- NRF51822+STM32bootload——typedef void (*Fun) (void) 理解
- MS17-010复现
- Discuz常见小问题2-如何修改管理员密码，修改admin账户密码