0

我阅读了 wiki 页面，但不明白为什么将较小的列表附加到较大的列表中很重要。

这是 wiki 页面中算法的一部分：

假设您有一个列表集合，并且每个列表的每个节点都包含一个对象、它所属的列表的名称以及该列表中的元素数。还假设所有列表中的元素总数为 n（即总共有 n 个元素）。我们希望能够合并这些列表中的任何两个，并更新它们的所有节点，以便它们仍然包含它们所属的列表的名称。合并列表 A 和 B 的规则是，如果 A 大于 B，则将 B 的元素合并到 A 中并更新曾经属于 B 的元素，反之亦然。

4

3 回答 3

1

Union-Find 只是一种让您保持谁是某个集合的“领导者”的方法。

例如，假设您有 5 个人 A、B、C、D、E。

最初，每个都从自己的集合开始，因此您可以像这样编写代码：

for each person in people:
    parent[person] = person

这样，您可以将每个人都设置为自己集合的领导者。

这应该是这样的：

{A}   {B}   {C}   {D}   {E}

我们需要的第一个操作是能够找到一个集合的领导者，这个操作被称为find。

然后我们陷入了一个属性：领导者是其自己的父母。

有两种可能性，或者这个人是它自己的父母，或者不是。

如果是，那么它就是该集合的领导者。

如果不是，那么我们将向它的父级询问同样的事情（如果它是它自己的父级），这样就可以了。

你可以这样编码：

find_leader_of(person P){
    if(parent[P] == P) return P
    else return find_leader_of(parent[P])
}

然后我们进行union操作，无非是在一组中转 2 个不相交的组。

假设你有这种情况：

{A, B}        {C, D}         {E}

而你做到union(B, D)了，那么会发生什么？

首先你需要找到两组的领导者：

fst_leader = find_leader_of(B)
snd_leader = find_leader_of(D)

然后你选择这些领导者中的任何一个作为另一个领导者：

parent[snd_leader] = fst_leader

这导致：

union(person P1, person P2){
    fst_leader = find_leader_of(P!)
    snd_leader = find_leader_of(P2)
    parent[snd_leader] = fst_leader
}

还有其他改进 union-find 的方法和其他方法来选择谁将成为谁的领导者，但这是您必须了解的基础知识，以便了解 union-find 是关于什么的。

于 2017-01-24T20:18:24.470 回答
0

这描述了一种执行更新操作的简单方法，您将在其中迭代一个列表中的所有元素并更改标签。

迭代较短的列表会更快，因此将较小的列表合并到较大的列表中是有意义的。

请注意，wiki 页面继续为不相交的集合数据结构描述了更有效的方法，其中哪个列表更长不再重要。

于 2017-01-24T19:38:03.687 回答
0

除非您想使用天真的方法，否则您可能需要查看 Hoshen-Kopelman 算法https://www.ocf.berkeley.edu/~fricke/projects/hoshenkopelman/hoshenkopelman.html - 它的摊销复杂度为N*A（其中 A 是反阿克曼函数——它渐近接近常数 6）。换句话说，它是 WICKED FAST。

如果我没记错的话，许多人在倒塌树木时关注了整体效率 - 即何时这样做是最有效的。我无法向您指出这些研究，但我确实记得十年前在教科书中读过它们。

希望这可以帮助。

于 2018-01-12T14:28:18.217 回答