联合查找：高效地检索集合中的所有成员 [英] Union-Find: retrieve all members of a set efficiently

问题描述

我正在使用 union-find 算法。在我的程序的第一部分，该算法计算一个大集合 E 的分区。

I'm working with an union-find algorithm. In the first part of my program, the algorithm computes a partition of a big set E.

之后，我想检索集合 S 的所有成员，其中包含给定的节点 x 。

After that, I want to retrieve all the members of the set S, which contains a given node x.

到目前为止，天真地，我正在测试 E 的所有元素的成员资格到 S 。但是昨天我正在阅读算法介绍（CLRS第3版，前言21.3-4），在练习中，我发现：

Until now, naively, I was testing membership of all elements of E to the set S. But yesterday I was reading "Introduction to Algorithms" (by CLRS, 3rd edition, ex. 21.3-4), and, in the exercises, I found that:

假设我们希望添加一个操作 PRINT-SET（x），这是
给定一个节点 x ，并以任何顺序打印 x 的所有成员。
显示如何只将一个属性添加到
disjoint-set林中的每个节点，以便 PRINT-SET（x）需要时间线性在
的成员中，$ code> x 的集合，
其他操作的渐近运行时间不变。

Suppose that we wish to add the operation PRINT-SET(x), which is given a node x and prints all the members of x's set, in any order. Show how we can add just a single attribute to each node in a disjoint-set forest so that PRINT-SET(x) takes time linear in the number of members of x's set, and the asymptotic running times of the other operations are unchanged.

线性数量 x 的集合将成为我的一个很大的改进问题！所以，我试图解决这个exersice ...并且在一些不成功的尝试后，我要求帮助Stack Overflow！

"linear in the number of members of x's set" would be a great improvement for my problem! So, I'm trying to solve this exersice... and after some unsuccessful tries, I'm asking help on Stack Overflow!

推荐答案

回想一下，union-find被实现为倒置树，其中对于每个集合S = {v 1> ，v ₂ ，...，v _n }，您有v _{n - 1} 边，最终具有相同的根（或 sink ）。

Recall that union-find is implemented as upside-down tree, where for each set S = {v₁, v₂, ..., v_n}, you have v_{n - 1} edges, that ultimately have the same root (or sink).

现在，无论何时向此树添加边（v _i ，v _j ），添加另一个边（使用新属性）（v < sub> j ，v ）。当您删除节点时，也删除该属性。

Now, whenever you add an edge (v_i, v_j) to this tree, add another edge (using the new attribute) (v_j, v_i). And when you remove a node, remove the attribute as well.

请注意，新的边缘与旧的分隔。当您打印集中的所有元素时，仅使用 。并且在原始算法中修改任何原始边缘时进行修改。

Note that the new edge is separated from the old one. You use it only when printing all elements in a set. And modify it whenever any original edge is modified in the original algorithm.

请注意，此属性实际上是节点列表，但总数所有列表中的元素数量仍然是 n - 1 。

Note that this attribute is actually a list of nodes, but the total number of elements in all lists combined is still n - 1.

这将给你一个第二个树，但不会颠倒。现在，使用根，并进行一些树遍历（使用例如 BFS 或< a href =http://en.wikipedia.org/wiki/Depth-first_search =nofollow noreferrer> DFS ），您可以打印所有元素。

This will give you a second tree, but not upside down. Now, using the root, and doing some tree-traversal (using e.g. BFS or DFS), you can print all elements.

这篇关于联合查找：高效地检索集合中的所有成员的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！