算法学习——kruskal重构树
2024-08-27 05:23:44
kruskal重构树是一个比较冷门的数据结构。
其实可以看做一种最小生成树的表现形式。
在普通的kruskal中，如果一条边连接了在2个不同集合中的点的话，我们将合并这2个点所在集合。
而在kruskal重构树中，如果一条边连接了在2个不同集合中的点，我们将新建一个节点出来，并用这个新节点作为一个中转连接这2个集合。
如图就是一棵kruskal重构树，方点表示新建出的节点，圆点是原图中的点，方点点权即边权。
这样建出的树会有一些美妙的性质，例如往上走点权是递增的，原图中的每个点都是叶子节点等。
当然一个更重要的是，如果我们要在最小生成树上求一些东西，这些建出的方点可以给我们提供方向。
原因就是我们每次都将新建的节点作为父亲，那么这些节点将会引导每个原图中的节点一步步向上，从而形成一个有根树，而且由于每个点被新建出的顺序将直接决定它的深度等信息，这棵树会有很多奇妙的性质。
例如我们可以一直向上走，找到某个节点使得这个节点即以下的点都满足点权小于k，这样我们就可以筛选出满足互相到达不会经过超过k的权值的边的点对。
当然也可以有别的用法，于是我们就可以快速的筛选出最小生成树上满足具有某些性质的节点。
同时kruskal重构树也将平时隐藏在并查集里的一些关系提出来放在了树里，因此也可以看做kruskal重构树其实是维护了一个类似并查集的关系
最新文章
- javaweb优化
- Android layout_weight理解
- 使用二分法查找mobile文件中区号归属地
- Android ListView 常用技巧
- Python开发【第六章】：Python面向对象
- C语言使用宏实现２个变量的交换
- 解构控制反转（IoC）和依赖注入（DI）
- WCF服务部署到IIS上，然后通过web服务引用方式出现错误的解决办法
- CQOI2015 选数
- 听说你的MES系统又失败了？
- c/c++再学习：排序算法了解
- Python&R&量化 金融之路
- linux局域网内挂载其它操作系统目录
- Golang package
- python linux 下开发环境搭建
- spark 源码阅读博客
- PAT 天梯赛 是否完全二叉搜索树   (30分)（二叉搜索树 数组）
- noip第9课作业
- [转帖]TLS 1.3概述
- 【笔记】jQuery插件开发指南