4,699 views
2 votes
2 votes
I have seen many varients of complexities using diferent data structures in implementing Kruskal Agorithm.  Can you pls post standard algorithm and tells me in details how to derive the complexities.  Please also mention the variations possibles when data structure changes and How will effect the complexity taking Best case and Worst case senarios .

1 Answer

3 votes
3 votes

Kruskal algorithm is just used to find mininum spanning tree  from the graph wich gives total minimum cost out of  all spanning tree.

Also it is possible a graph can have more the one spanning tree with same minimum cost.

Its a greedy algorithm , not a dynamic programming solution.

KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3    MAKE-SET(v)
4 foreach (u, v) in G.E ordered by weight(u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION(u, v)
8 return

Let me explain how it works,  Let  E be the number of edges present in the graph ,  this algorithm also depends on number of edges, lower the number of edges in the graph faster the algorithm works

Firstly we want the edges in increasing order by weight.

So, just sort the edges, best sorting algorithm with N elements take O(N log N ) time only when we are not using counting sort ( linear time algorithm )  because weight of edges may be high , then its difficult to use hashing as in case of counting sort.

So it will take E Log E time , where E = number of edges in the graph => O(E log E )   

If weight are low then we can use linear time sorting algorithm in O(E) 

Now,  traverse all edges one by one .

Let say current edges is ( U - > V ) ,  then we have to check whether U and V  belong to same component or not , if they are in same component then we have to exclude that edge from our minimum spanning tree , because adding this edge may creat cycle.

If Make_set(U) is not equals to Make_set(V)  then , it means these nodes are not in the same component, we can add this edge in our spanning tree , and increment our cost with the edge wieght. and then we have to merge both the component , 

component 1 which contain node U with component 2 with node V.   

Only left part is, how to find whether which nodes is belong to which component and how to merge component. 

Total complexity : Sorting time +   edge traversel *  (Merging operation +  find_component_operation ) 

Disjoint Set union data structure are  designed to  handle (merging_operation  +  finding_component_) 

Link for dsu data structure : https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/ 

We can hadle merging  + finding component  in O(N) or   O(logN) cost  

Variation :  

complexity : sorting +   edges * (merging_operation  +  finding_component ) 

1st case sorting in O(E) 

Complexity :  E  +  E * N  ,   E + E * logN 

2nd case sorting in O(E log E )

Complexity : E log E +  E * N ,  E log E + E * log N ,     

Best complexity is ELog E or eqquivalently ElogN ( because E is atmost N^2 , then  E log N^2  =  2 * E Log N = E log N )  

If number of edges are almost linear very less then N ^ 2 , then   E is equlas to N  , then best complexity is N Log N. 

Related questions

5 votes
5 votes
3 answers
1
Kapil asked Jan 24, 2017
3,355 views
It may be the case that "Kruskal's Algorithm may not maintain connectivity while Prim's algorithm always does that" ?Any example which favours this ?
0 votes
0 votes
2 answers
3
rahul sharma 5 asked Dec 15, 2016
792 views
Consider a graph with V vertices and e edges,What is the worst case time complexity for kruskal's algorithm when implemented using array data structure?a.) E+ElogVb.)Vlog...