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.