data structures - Does using union-find in Kruskal's algorithm actually affect worst-case runtime? -

so i'm teaching myself graph algorithms, on kruskal's, , understand it's recommended use union-find checking whether adding edge creates cycle takes o(log v) time. practical purposes, see why you'd want to, strictly looking through big o notation, doing affect worst-case complexity?

my reasoning: if instead of union find, did dfs check cycles, runtime o(e+v), , have perform v times runtime of o(v^2 + ve). it's more union find, o(v * logv), bulk of complexity of kruskal's comes deleting minimum element of priority queue e times, o(e * loge), big o answer. don't see space advantage either since union-find takes o(v) space , data structures need maintain find cycle using dfs.

so overly long explanation simple question: using union-find in kruskal's algorithm affect worst-case runtime?

and understand it's recommended use union-find checking whether adding edge creates cycle takes o(log v) time

this isn't right. using union find o(alpha(n) * m), alpha(n) inverse of ackermann function, and, intents , purposes, can considered constant. faster logarithmic:

since alpha(n) inverse of function, alpha(n) less 5 remotely practical values of n. thus, amortized running time per operation small constant.

---

but bulk of complexity of kruskal's comes deleting minimum element of priority queue e times

this wrong. kruskal's algorithm not involve using priority queues. involves sorting edges cost @ beginning. although complexity remains 1 mention step. however, sorting might faster in practice priority queue (using priority queue will, @ best, equivalent heap sort, not fastest sorting algorithm).

bottom line, if m number of edges , n number of nodes.:

1. sorting edges: o(m log m).

2. for each edge, calling union-find: o(m * alpha(n)), or o(m).

3. total complexity: o(m log m + m * alpha(n)).

4. if don't use union-find, total complexity o(m log m + m * (n + m)), if use o(n + m) cycle finding algorithm. although o(n + m) step understatement, since must update structure somehow (insert edge). naive disjoint-set algorithm o(n log n), worse.

note: in case, can write log n instead of log m if prefer, because m = o(n^2) , log(n^2) = 2log n.

in conclusion: yes, union-find helps a lot.

even if use o(log n) variant of union-find, lead o(m log m + m log n) total complexity, assimilate o(m log m), in practice you'd rather keep second part faster if can. since union-find easy implement, there's no reason not to.