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 Borůvka’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) {
	auto o = std::ranges::to<std::vector>(std::views::iota(0, m));
	std::ranges::sort(o, {}, [&](int i) -> int {
		return w[i];
	});
 
	DSU dsu(n);
	return std::ranges::fold_left(o | std::views::transform([&](int i) -> int {
		return dsu.merge(u[i], v[i]) * w[i];
	}), 0, std::plus());
}