联合发现不相交集加权快速联合与路径压缩算法
共有2个答案
我将首先引用几个基本点。首先，这是实现不相交集的最佳算法，称为带路径压缩启发式的秩并算法。该算法需要2个数组，第一个（id[]）用作到父节点的链接，第二个（iz[]）给出了该集合的节点数int。
我们有两个业务-联合和连接。
联合是通过“排序”完成的，通过使较小的树成为较大的树的子树，这导致了进一步操作的较低摊余成本，因此长度趋于最小。
当调用连接方法时，在我们了解该树的根之后，我们使用路径压缩技术，该技术基本上将该特定节点指向该树的根，因此将来我们不必再次遍历整个分支。由于 iz[] 只包含该集的节点数，因此它不会受到路径压缩的任何影响。
就我对代码的理解而言，数组iz[]表示给定不相交集合中元素的数量。当您压缩路径时，您不会为每个集合修改该数字。因此，路径压缩不会影响iz[]数组。
-
我有一个项目，我必须实现一个带有路径压缩算法的加权快速并集。在看到其他一些源代码后，我最终得到了这个： 分配给我的任务是正确完成以下方法: int find（int v） void unite（int v，int u） setCount（int v） 嗯，算法似乎很慢，我找不到合适的解决方案。
-
根据Princeton booksite，带有路径压缩的加权快速联合将10^9联合对10^9对象的操作时间从一年减少到大约6秒。这个数字是怎么得出的？当我在10^8操作中运行下面的代码时，我的运行时间是61s。
-
我正在为联合/查找结构实现快速联合算法。在“Java中的算法”一书网站上给出的实现中，普林斯顿实现在实现路径压缩（在方法中）时无法保持树的大小不变。这不应该对算法产生不利影响吗？还是我错过了什么？另外，如果我是对的，我们将如何修改大小数组？
-
我这个星期天要参加考试，我只想确认我正在做的事情是否正确（你知道考试让我持怀疑态度） 这就是算法的工作原理： 这就是问题所在： 回想一下为不相交集开发的算法，这些不相交集来自一组n个元素。查找使用路径压缩，联合使用排名。此外，相同等级的两棵树的联合选择与第二个参数关联的根作为新根。从一个集合S={1,2，…，10}和10个不相交子集开始，每个子集都包含一个元素。a.执行后绘制最后一组树： Unio
-
我正在学习联合/查找结构的“加权快速联合与路径压缩”算法。普林斯顿edu网站详细解释了该算法。这是Java的实现： 但就像网站提到它的性能一样： 定理：从空数据结构开始，任何 M 并集序列和对 N 个对象的查找操作都需要 O（N M lg* N） 时间。 证明非常困难。 但是算法仍然很简单！ 但我仍然很好奇迭代对数lg*n是如何产生的。它是如何推导出来的？有人可以证明它或只是以直观的方式解释它吗？
-
有一种“带路径压缩的加权快速联合”算法。 代码： 问题： > 路径压缩是如何工作的意味着我们只到达节点的第二个祖先，而不是根。 包含从 到 整数。如何帮助我们知道集合中元素的数量？ 有人能帮我澄清一下吗？