В реализации Java алгоритма Крускала, где именно мы должны выполнить Path Compression?

Question

При реализации алгоритма Крускала в Java с использованием наборов Disjoint следует ли называть сжатие пути отдельной функцией или она должна быть неотъемлемой частью функции find()?

Answer 1

Сжатие пути и другие оптимизации, такие как объединение по рангу, должны применяться каждый раз, когда вы вызываете find операция над вашим непересекающимся лесом.

Один из способов увидеть это: с точки зрения алгоритма Крускала, вам просто нужно уметь вызывать find а также union и пусть они работают правильно. Вам не нужно беспокоиться о деталях того, как вы делаете find а также union работать правильно, только то, что они делают. Ответственность за то, чтобы все работало быстро, лежит на несвязанном наборе леса, поэтому find где вы увидите сжатие происходит.