# Kruskal's Algorithm

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
```