Kruskal's Algorithm

computation graph-theory algorithms

Definition

Kruskal's Algorithm

Kruskal’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected network. It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

For sparse graphs, where $|E|=\Theta (|V|)$, Kruskal’s algorithm typically performs better than Prim’s algorithm.

Logic and Implementation

Kruskal’s algorithm treats every vertex as a separate tree and progressively merges them by adding the shortest available edge that does not form a cycle.

1. Sort all edges in the graph by their weight in non-decreasing order.
2. Initialise a forest where each vertex is a separate disjoint set (using the union-find data structure).
3. Iterate through the sorted edges:

• For each edge $(u,v)$, check if $u$ and $v$ belong to different sets (using $\mathrm{find}$).
• If they do, add the edge to the MST and merge the two sets (using $\mathrm{union}$).
• If they belong to the same set, discard the edge to avoid a cycle.

Runtime

The efficiency of Kruskal’s algorithm is largely determined by the sorting step and the performance of the union-find operations.

Step	Time Complexity
Edge Sorting	$O(\Vert E\Vert \log \Vert E\Vert )$ or $O(\Vert E\Vert \log \Vert V\Vert )$
Union-Find Operations	$O(\Vert E\Vert \cdot \alpha (\Vert V\Vert ))$
Total Complexity	$O(\Vert E\Vert \log \Vert V\Vert )$

Where $\alpha$ is the inverse Ackermann function, which grows so slowly that it is effectively constant for all practical purposes.