Kruskal's Algorithm

Kruskal’s Algorithm is an algorithm that computes the weight of the minimum spanning tree of a connected undirected graph $G=(V,E)$ with edge weights in $\mathcal{O}(|E|\log |E|)$ time and $\mathcal{O}(|E|)$ space.

Tip

This problem can also be solved by Prim’s Algorithm in

• $\mathcal{O}(|V{|}^2+|E|)$ time and $\mathcal{O}(|E|)$ space, or
• $\mathcal{O}(|E|\log |E|)$ time and $\mathcal{O}(|E|)$ space.

Tip

This problem can also be solved by Boruvka’s Algorithm in $\mathcal{O}(|E|\log |V|)$ time and $\mathcal{O}(|E|)$ space.

Algorithm

Lemma

Let $\mathcal{T}$ denote the set of minimum spanning trees of $G$, then

$$\forall e\in \arg \underset{e\in E}{\min }w(e),\exists T\in \mathcal{T},e\in E(T)$$

Proof

Let $T$ be an arbitrary minimum spanning tree of $G$.

If $e\notin E(T)$, let $C$ be the cycle in $T+e$, $f$ be an edge in $C\setminus \{e\}$. Then since $w(f)\ge w(e)$, it follows that $T+e-f$ is a minimum spanning tree containing $e$.

0. Select an edge $e$ in $\arg {\min }_{e\in E}w(e)$.

1. Solve for the graph obtained by contracting edge $e$ recursively.

Applying the lemma yields that the selected edges form a minimum spanning tree.

Applying an appropriate sorting algorithm (e.g., Merge Sort, Heapsort, Quicksort) to sort the edges and using a Disjoint Set Union to maintain the structure of the graph yield an algorithm that solves the problem in $\mathcal{O}(|E|\log |E|)$ time and $\mathcal{O}(|E|)$ space.

int kruskal(int n, int m, const std::vector<int> &u, const std::vector<int> &v, const std::vector<int> &w) {
	std::vector<int> o(m);
	std::iota(o.begin(), o.end(), 0);
	std::ranges::sort(o, std::less(), [&](int i) -> int {
		return w[i];
	});
 
	DSU dsu(n);
	int sum = 0;
 
	for (int i : o) {
		if (dsu.merge(u[i], v[i])) {
			sum += w[i];
		}
	}
 
	return sum;
}