Kruskal's Algorithm

#programming #algorithms

See also : Prim's Algorithm

Question

Find the Minimum Spanning Tree of a connected, undirected, weighted graph.

What it mean

Imagine an undirected, connected graph, you are given it's vertices and it's weighted edges.

The goal is to :

Connect all vertices using some of the edges such that

1. The graph is still connected.
2. There are no cycles (ie, it's a tree)
3. The total sum of edge weights is minimum

Mental model

Imagine a collection of multiple cities, and a road network that connects them, with each road having a cost.

What we require is a way to connect all cities using the least total cost, without building unnecessary roads.

Spanning : Connects all vertices
Tree : Without a single cycle.
Minimum : Total cost is minimized.

Approach

Given all the sorted edges, keep picking minimum weight edges so as long as this selection does not make a cycle. Terminate when $V-1$ edges are picked.

This is a greedy approach

Therefore, it has to maintain knowledge of what component the current node belongs to, and whether adding an edge will connect two different components. If yes, add it, if not, skip (it will create a cycle).

Key problem :

How do we efficiently check if the node $u$ and $v$ are part of two different components?

Solution : Disjoint set (Union find)

We maintain components using the following

• find(x) $⟹$ find which component node $x$ belongs to
• union(x,y) $⟹$ merge two components if an edge is connecting them

This can be thought of as building individual trees, and then connecting them down the line using the minimum weight.

• TODO : Understand the working of union subsets used in kruskals, and write down psuedo or C-code here for future reference.

Time complexity $$O(E\log E)$$

In all cases. Best, average and worst.

Space complexity is also same in all cases, $O(V+E)$