Kruskal's Algorithm

From Algorithmist
Jump to navigation Jump to search

Kruskal's algorithm is an algorithm for efficiently finding a Minimum Spanning Tree of an undirected graph. Kruskal's Algorithm and Prim's Algorithm are the two main algorithms for finding a minimum spanning tree. Intuitively, Kruskal's algorithm proceeds by starting with an empty subgraph, then iteratively adding the edge of least weight that hasn't been added and does not create a cycle, until a minimum spanning tree is achieved.

 1  function Kruskal(G)
 2    for each vertex v in G do
 3      Define an elementary cluster C(v) ← {v}.
 4    Initialize a priority queue Q to contain all edges in G, using the weights as keys.
 5    Define a tree T ← Ø       //T will ultimately contain the edges of the MST
 6     // n is total number of vertices
 7    while T has fewer than n-1 edges do
 8      // edge u,v is the minimum weighted route from/to v
 9      (u,v) ← Q.removeMin()
10      // prevent cycles in T. add u,v only if T does not already contain an edge consisting of u and v. 
11      // Note that the cluster contains more than one vertex only if an edge containing a pair of
12      // the vertices has been added to the tree.
13      Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
14      if C(v) ≠ C(u) then
15        Add edge (v,u) to T.
16        Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).
17    return tree T

External Links[edit]