While implementing Kruskal's algo in Java using Disjoint sets, should we call path-compression as separate funtion or it should be integral part of the find() funtion?
Path compression and other optimizations like union-by-rank should be applied any time you call the find
operation on your disjoint-set forest.
One way to see this: from the perspective of Kruskal's algorithm, you just need to be able to call find
and union
and have them work correctly. You shouldn't need to worry about the details of how you're making find
and union
work correctly, just that they do. It's the responsibility of the disjoint-set forest to ensure that everything runs quickly, and so the calls to find
are where you'll see the compression occurring.