关于这个关于联合查找不相交集的问题，加权快速联合与路径压缩算法
路径压缩是否会影响 iz[] 数组（包含以 i 为根的树的长度的数组）？
问问题
879 次
2 回答
2
据我对代码的理解，数组 iz[] 表示给定不相交集中元素的数量。压缩路径时，您不会修改每组的该数字。因此，路径压缩不会影响 iz[] 数组。
于 2013-08-28T11:59:43.507 回答
2
我将开始引用一些基本观点。首先，这是实现不相交集的最佳算法，并通过路径压缩启发式按秩称为联合。该算法需要 2 个数组，first(id[] there) 用作到 parent 的链接，第二个(iz[]) 给出该集合的节点数。
我们有 2 个操作 - 联合和连接。
联合是由“等级”完成的，通过使较小的树成为较大的树的孩子，从而降低进一步操作的摊销成本，这样长度往往是最小的。
当调用 connected 方法时，在我们知道那棵树的根之后，我们使用路径压缩技术，它基本上将该特定节点指向那棵树的根，因此将来我们不必再次遍历整个分支。由于 iz[] 仅包含该集合的节点数，因此它对路径压缩没有任何影响。
于 2013-08-29T04:12:17.943 回答