java - 在 Kruskal 算法的 Java 实现中，我们究竟应该在哪里执行路径压缩？

Question

在使用不相交集在 Java 中实现 Kruskal 算法时，我们应该将路径压缩称为单独的函数还是应该是 find() 函数的组成部分？

标签： javaminimum-spanning-treekruskals-algorithmdisjoint-sets

Answer 1

find每当您在不相交集森林上调用操作时，都应应用路径压缩和其他优化，例如按等级联合。

一种看待这一点的方法：从 Kruskal 算法的角度来看，您只需要能够调用find并union让它们正常工作。你不应该担心你如何制作find和union正确工作的细节，只要他们这样做。确保一切快速运行是不相交集林的责任，因此调用find是您将看到压缩发生的地方。