Kruskal Algorithm

Question

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are unsorted is _______

______________________________________________________________________________

If elements are sorted we do with Union Find algo with inverse of Ackermann function i.e.$O\left (|E|.\alpha |V| \right )$ , where $\alpha |V|$ is $log^{*}V$

Now from here can we derive it for unsorted edges?

for ref: here

Comments

if edge weights  are unsorted then running time $\epsilon$ O(sort(|E|) + |E|*$\alpha$(V) + |V|) using Disjoint-Set data structure..

If edge weights are small like {1,2,3,....n^c} , Then we can  use radix sort for sort(|E|) and it will take linear time in terms of number of edges , otherwise Prim's algo will be better...

 

---

What if fibonacci heaps are used?

Answer 1

O(E + VLOGV) - BEST CASE

0(ELOGV) - WORST CASE

Comments

can you tell what are best and worst cases?