时间戳

首页 > 解决方案 > 如何在 UnionFind 数据结构中正确实现加权联合和路径压缩

data-structures - 如何在 UnionFind 数据结构中正确实现加权联合和路径压缩

问题描述

我正在尝试在 C 中实现 Union-Find/Disjoint-Set 数据结构，在 Find 中使用加权联合和路径压缩。与非加权联合相比，我对如何实施加权联合以降低时间复杂度有一些疑问。

我已经在网上找到了几个解决这个问题的方法，并实现了我自己的。在每个解决方案中，每个单独树的根（代表一个集合）始终保存树的节点数。当联合属于不同集合的两个随机对象的集合时，首先找到根（这里使用路径压缩），然后我们比较这些根的大小。最大树的根被设置为最小树的根的父节点。

然而，在我的理解中，我们试图通过加权联合来实现的是降低生成树的高度（这也是我们试图通过路径压缩来实现的）。因此，应该连接到另一棵树的不是节点数最少的树，而是高度最低的树。这将高度保持在最低限度。

它是否正确？考虑到实现的其余部分，检查高度和大小是否等效（我们总是从多个单个（一个节点）集开始）？

假设需要检查的是高度，那么在不使用路径压缩的情况下跟踪树的高度是相当简单的。然而，当使用路径压缩时，我还没有找到一种方法来跟踪树的高度（至少在不遍历整个树的情况下不会，这会增加“查找”算法的时间复杂度。

这是我发现并使用我在 C++ 中描述的（与我编码的非常相似）的实现示例： https ://github.com/kartikkukreja/blog-codes/blob/master/src/Union%20Find %20(不相交%20Set)%20Data%20Structure.cpp

标签： data-structurestreetime-complexitydisjoint-setsunion-find

解决方案

看起来你自己已经想通了。

Union-by-height 是制作最短树的明显方法，但是当您使用路径压缩时很难跟踪高度......

因此，通常使用按等级联合。如果我们不进行任何路径压缩，集合的“等级”就是它的高度，所以当您使用路径压缩的等级联合时，就像从高度联合开始，然后应用路径压缩为优化，确保路径压缩不会改变合并的工作方式。

然而，很多人（包括我自己）使用 union-by-size，因为大小通常很有用，并且可以证明 union-by-size 产生与 union-by-rank 相同的最坏情况复杂性。同样在这种情况下，路径压缩不会影响合并，因为它不会改变任何根的大小。

推荐阅读