Kruskal's Algorithm
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