Does it make sense to apply path compression to kruskal algorithm?

Question

I am reading about Kruskal and analysing it’s time complexity.

Let’s say there are E edges and V vertices. Kruskal algorithm has two important time complexity equations ,

1. Sort edges- Elog(E)
2. For whether edge from v1->v2 , apply find(v1) and find(v2). If cycle exist don’t connect. Other wise connect them. - E*timecomplexity(find(v))

Now in the second step , time complexity of find(v) will be O(v) for skewed sets. We can improve it by using union by rank where we append small to talk in term a of height, O(log(v)).

Now my question is can we apply path compression here to further reduce find operation time complexity further to O(α(n)) (where α is the inverse of the Ackerman function). ? Wouldn’t path compression distort the graph itself as we will be re arranging the edges!!

So I believe best case for union and find Is -> E(log(V))

I am thinking time complexity without path compression using union by rank is , O(ElogE)(sort) +O(Elogv)(find and union) that would be upperbound O(ElogE)

Am i right here ? Or we can use path compression here ??

Answer 1

You can apply path compression, as the structure Union-Find does not change the structure of the graph at all (with or without path compression).

The structure is only there to check efficiently if two vertices are in the same connected component, but the "edges" in the tree representation of the structure union find are unrelated to the edges in the minimum spanning tree.

Though path compression is quite easy to implement and improve time complexity, as you have stated the overall time complexity does not change, because the first step (sorting edges) is the one that takes the longest time.

However, with further hypotheses on the weights, it could be possible to sort edges in linear time (using radix sort for example). In that case, path compression would decrease the overall time complexity.