在 Kruskal 算法的 Java 实现中,我们究竟应该在哪里执行路径压缩?



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

每当在脱节集林上调用find操作时,都应应用路径压缩和其他优化(如按秩联合)。

一种看法是:从Kruskal算法的角度来看,你只需要能够调用findunion并让它们正常工作。您不必担心如何使findunion正常工作的细节,只需担心它们确实如此。不相交集林负责确保一切快速运行,因此对find的调用是你会看到压缩发生的地方。

最新更新