Back

Table of contents

Next

Kruskal's algorithm

   Kruskal's algorithm is based directly on the generic minimum-spanning tree algorithm. It finds a safe edge to add to the growing forest by finding, of all edges that connect any two trees in the forest, an edge (u,     v) of least weight.

   Kruskal's algorithm uses a disjoint-sret data structure to maintain several disjoint sets of elements. Each set contains the vertices in a tree of the current forest. The operation FIND-SET(u) returns a representative element from the set that contains u.Thus,  we can determine whether two vertices belong to the same tree or not by testing whether FIND-SET(u) equals FIND-SET(v) or not. The combining of trees is accomplished by the UNION procedure.
 

MST-KRUSKAL(G, w)

   1   A <- empty
   2   for each vertex v belonging to V[G]
   3            do MAKE-SET(v)
   4   sort the edges of E by nondecreasing weight w
   5   for each edge (u, v) belonging to E, in order by nondecreasing weight
   6           do if FIND-SET(u) != FIND-SET(v)
   7                    then A <- A U {(u, v)}
   8                              UNION(u, v)
   9   return A

    Lines 1-3 initialize the set A to the empty set and create | V | trees, one containing each vertex. The edges in E are sorted into order by nondecreasing weight in line 4. The for loop in lines 1-4 checks, for each edge (u, v), whether the endpoints u and v belong to the same tree. If they do, then the edge (u, v) cannot be added to the forest without creating acycle, and the edge is discardede.Otherwise, the two vertices to different trees, and the edge (u, v) is addedto A in line 7, and the vertices in the two trees are merged in line 8.

   The running time of Kruskal's algorithm for a graph G = (V, E) depends on the implementation of the disjoint-set data structure. Initialization takes O(V), and the time to sort the edges in line 4 is O(E lg E). There are O(E) operations on the disjoint-set forest, which in total take O(E g(E, V)) time, where g is the functional inverse of Ackermann's function. Since g(E, V) = O(lg E) , the total running time of Kruskal's algorithm is O(E lg E).