在做算法实验（图论-桥问题）的时候想优化并查集效率，于是翻看算法导论的并查集部分（p329）发现里面提到“通过引入两种启发式策略（按秩合并和路径压缩），我们能得到一个渐近最优的不相交集合数据结构”。这里的路径压缩比较常见，但是按秩合并见的较少，理解起来也不那么容易。 按秩合并就是让具有较少结点的树的根指向具有较多结点的树的根，这里算法导论并没有简单粗暴的直接记录结点数量，而是采用了对每个结点维护一个秩的方法，秩表示该结点高度的一个上界。 原文中具体的描述如下： 按秩合并的具体算法步骤如下： (1)初始化一个数组，记录每个结点的秩，初始都为0 (2)当进行union操作时，需要比较该边两个结点的最终父节点（即树根）的秩： A. 如果两个根的秩相同，任意选择一个根作为父节点，并且让该父节点的秩加1 B.如果秩不同，将秩小的根的父节点设置为秩大的根，但是秩不用进行任何修改 具体的伪代码如下： 路径压缩比较常见，就是在FIND过程中把途经的点的直接父节点都设置为最终父节点（根）。 路径压缩的实现可以使用非递归、递归两种，递归写法更简练，用的比较多。 根据算法导论所说，如果单独使用按秩合并、路径压缩其中的一种，都能一定程度改善并查集的效率，但是两种方法一起使用可以让效率达到极致。 同时使用按秩合并、路径压缩的最坏情况为O( m a(n) )，m是总的操作数（包括makeset，union，find），n是结点数。 a(n)是一个增长非常慢的函数，任何情况下都小于等于4，因此可以认为总的时间复杂度是和m成线性关系，具体证明见算法导论。
按秩合并
实现
路径压缩
实现
启发式策略的效率提升
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
