March 10, 2019

Kruskal’s algorithm is an algorithm for finding minimum spanning trees - how to connect all nodes in a graph while keeping the sum of edge weights the smallest.

Take a look at this graph!

In every iteration of our algorithm, we select the edges with the smallest weights that don’t create a cycle. So in the first iteration, our selection goes like this:

The next step needs a little more thought. We have 3 edges here that all have a weight of 2 - $AF$, $CE$ and $CD$. We can arbitrarily choose one of them in this case, so for example, I choose $CE$.

Now, among all the remaining edges, 2 is still the smallest weight. However, $CD$ will create a cycle for us, so we should add this edge to our black list and continue - add $AF$ to our selection.

With all the edges of weight 2 being dealt with, the next step is pretty straightforward.

Then finally selecting $BD$ to connect all nodes inside a same tree.

And that’s it! We have found our minimum spanning tree with Kruskal’s algorithm!

```
Procedure kruskal(E, T : Sequence of Edge, P : UnionFind)
sort E by increasing edge weight
foreach {u, v} ∈ E do
if u and v are in different components of P then
add edge {u, v} to T
join the partitions of u and v in P
```

The time complexity of this algorithm is $O((n+m)\cdot log\ m)$.