CODEWITHSUNDEEP
data-structurestreeminimum-spanning-treekruskals-algorithmunion-find
thePIVOT
thePIVOT

Reputation: 33

Union find algorithm in Kruskals algorithm

How does these two functions work ?

The time complexity of the function find is O(log n) assuming that the length of each chain is O(log n). In this case, the functions same and unite also work in O(log n) time. The function unite makes sure that the length of each chain is O(log n) by connecting the smaller set to the larger set.

Can someone explain how with an example ?

int find(intx) {
while(x != k[x]) x = k[x];
returnx;
}

bool same(inta,intb) {
returnfind(a) == find(b);
}

void unite(inta,intb) {
a = find(a);
b = find(b);
if(s[a] < s[b]) swap(a,b);
s[a] += s[b];
k[b] = a;
}

Upvotes: 0

Views: 146

Answers (1)

julieb
julieb

Reputation: 43

You get O(log n) complexity vs. O(n) because you're always connecting the smaller set to the larger set (vs. the larger to the smaller) in the unite() function. If one set is equal to or smaller than another, the biggest the smaller set can be is the size of the larger (worst case), but will often be smaller. For example, if there are 20 elements total, the two sizes could be 1 and 19, 2 and 18, all the down to 10 and 10. The net is that when you unite two clusters, it will, at most, double in size, which means it adds, at most one level to its depth. Hence, going up the tree will take at most log2N steps b/c that's the max depth.

Upvotes: 0

Related Questions