spanning-trees

kruskal

function

kruskal

{ u: string; v: string; weight: number; }[]

Kruskal’s Algorithm is an algorithm to solve the MST problem It constructs a MST by taking the globally lowest-weight edge and contracting it.

@complexityO(E lg E + Eα(V ))
  • T_sort(E) + O(V ) · T_makeSet + O(E)(T_find + T_union) = O(E lg E + Eα(V ))
  • T_makeSet is O(1) and T_find +T_Union is amortized O(α(V )) for Union-Find data structures.
  • Furthermore, if all weights are integer weights, or all weights are in the range [0, E^O(1)], then the runtime of the sorting step is O(E), using Counting Sort or a similar algorithm, and the runtime of Kruskal’s Algorithm will be better than that of Prim’s Algorithm.
@paramgraphWeightedGraph
@returns{ u: string; v: string; weight: number; }[]