Discovered in 1956 by Joseph B. Kruskal. This algorithm has a close association
with *clustering* algorithms. Clustering is a form of unsupervised learning that
extracts patterns from unlabeled data. While Prim’s algorithm is a bit easier to
implement, Kruskal’s algorithm has the added benefit of being able to calculate
the MST for a graph that is too large to fit in a single memory space.

## Asymptotic Complexity

$O((m+n)\log n)$

## Pseudo Code

### Naive Implementation

The pseudo code below is a particularly slow implementation ($O(mn)$) of Kruskal’s algorithm that utilizes a graph search algorithm. However, this simple implementation makes the algorithm easy to understand.

```
G = connected, undirected graph
MST = empty graph (will contain edges in MST)
E = array to hold sorted edges
All add vertices in G to MST
Add all edges in G to E
Sort E by weight in ascending order
// see BFS and DFS in Graph Search section
creates_cycle:
G = graph to search
v = starting vertex
w = end vertex
if graph search from v-> w == not found:
return false
else
return true
for each edge in E:
// Once we have n-1 edges, the MST is complete
if MST->m == (G->n - 1):
break
if creates_cycle MST e->tail e->head:
continue to next edge
add e to MST
return MST
```

### Union-Find-Based Implementation

This version is more complex, but results in a considerably faster run time ($O((m+n)\log n)$)

Invariants:

- Union-Find (
`U`

) data structure represents all connected components that have been added to the MST (`T`

)

```
G = connected, undirected graph
T = empty set (will contain edges in MST)
E = array to hold sorted edges
U = Empty Union-Find Data Structure
Initialize U with all vertices in G
Add all edges in G to E
Sort E by weight in ascending order
for each edge in E:
// Once we have n-1 edges, the MST is complete
if |T| == (G->n - 1):
break
// If a cycle is detected, move the next edge
if U->find e->tail == U->find e->head:
continue to next edge
else
U->union e->head e->tail
add e to T
return T
```

## Source Code

Relevant Files:

Click here for build and run instructions