Implementing Kruskal’s Algorithm in Go

Understanding Kruskal’s Algorithm in Go

Performance Benchmark: Kruskal vs Prim in Go

Sponsored

Your team in Shanghai can finally use the same drive as your team in Berlin. Sesame Disk by NiHao Cloud No VPN. No blocked links. Real-time sync across China, Europe, and the Americas — from $4/mo.

The difference in complexity influences which algorithm to choose. Kruskal’s algorithm sorts all E edges, which costs O(E log E), then performs one union-find operation per edge. Prim’s algorithm with a binary heap runs in O(E log V), with the complexity depending on E, as explained in this comparison of Kruskal and Prim. On a sparse graph where E is close to V, log E and log V are nearly the same, so the two bounds come close and constant factors determine which is faster. Kruskal’s sort is a single tight loop over a contiguous slice, which Go’s sort.Slice executes with good cache behavior. Prim’s heap performs a push and a pop for every accepted vertex and each of its neighbors, and each of those operations accesses a scattered heap array.

Graph type	Edges (approx.)	Kruskal (union-find)	Prim (binary heap)	Prim (array scan)
Sparse	E ~ V	O(E log E)	O(E log V)	O(V^2)
Moderate	E ~ V log V	O(E log E)	O(E log V)	O(V^2)
Dense	E ~ V^2	O(V^2 log V)	O(V^2 log V)	O(V^2)

Princeton’s Algorithms 4th edition reference confirms the Kruskal bound directly: it computes the MST of any connected edge-weighted graph with E edges and V vertices using extra space proportional to E and time proportional to E log E in the worst case. The eager Prim variant uses space proportional to V and time proportional to E log V. The table above follows that same source for the asymptotic costs.

To test this on your own hardware rather than relying on asymptotic analysis, generate synthetic graphs at varying density and run both implementations with Go’s built-in benchmark harness. The harness below uses deterministic weights so runs are reproducible.

Note: The following code is an illustrative example and has not been verified against official documentation. Please refer to the official docs for production-ready code.

package main

import (
	"math/rand"
	"testing"
)

// buildGraph returns an edge list and adjacency list for n vertices
// with approximately degree*n edges. Note: may produce a disconnected
// graph when degree is very small, in which case Kruskal returns a forest.
func buildGraph(n, degree int, rng *rand.Rand) ([]Edge, [][]item) {
	edges := make([]Edge, 0, n*degree)
	adj := make([][]item, n)
	seen := map[[2]int]bool{}
	for i := 0; i < n; i++ {
		for k := 0; k < degree; k++ {
			j := rng.Intn(n)
			if i == j {
				continue
			}
			a, b := i, j
			if a > b {
				a, b = b, a
			}
			key := [2]int{a, b}
			if seen[key] {
				continue
			}
			seen[key] = true
			w := rng.Intn(1000) + 1
			edges = append(edges, Edge{a, b, w})
			adj[a] = append(adj[a], item{w, b})
			adj[b] = append(adj[b], item{w, a})
		}
	}
	return edges, adj
}

func BenchmarkKruskal(b *testing.B) {
	rng := rand.New(rand.NewSource(42))
	edges, _ := buildGraph(5000, 4, rng) // sparse: E ~ 4V
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		KruskalMST(5000, edges)
	}
}

func BenchmarkPrim(b *testing.B) {
	rng := rand.New(rand.NewSource(42))
	_, adj := buildGraph(5000, 4, rng)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		PrimMST(5000, adj)
	}
}

Run with go test -bench=. -benchmem. On sparse graphs (degree 4), Kruskal’s total time is mostly spent in the single sort.Slice call, while lazy Prim pays heap push and pop costs on every accepted vertex and its neighbors. On dense graphs where degree approaches V, Kruskal’s sort step grows toward O(V^2 log V) because it creates and sorts every candidate edge, while the array-based Prim variant never builds the edge list and stays at O(V^2).

Implementation Complexity in Go: Practicalities and Pitfalls

The code is short, but a few production details affect whether it stays fast. The full Kruskal implementation below reads an edge list, sorts it by weight, and processes the list once.

package main

import (
	"fmt"
	"sort"
)

type Edge struct {
	From, To, Weight int
}

func KruskalMST(numVertices int, edges []Edge) (int, []Edge) {
	// Copy before sorting so the caller's slice is untouched.
	sorted := make([]Edge, len(edges))
	copy(sorted, edges)
	sort.Slice(sorted, func(i, j int) bool {
		return sorted[i].Weight < sorted[j].Weight
	})

	dsu := NewDSU(numVertices)
	mst := make([]Edge, 0, numVertices-1)
	totalWeight := 0

	for _, e := range sorted {
		if dsu.Union(e.From, e.To) {
			mst = append(mst, e)
			totalWeight += e.Weight
			if len(mst) == numVertices-1 {
				break
			}
		}
	}
	return totalWeight, mst
}

func main() {
	// 6 data-center nodes, 9 candidate fiber links with cost in dollars
	edges := []Edge{
		{0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},
		{2, 3, 4}, {2, 4, 6}, {3, 4, 5}, {3, 5, 7}, {4, 5, 8},
	}
	weight, mst := KruskalMST(6, edges)
	fmt.Println("total cost:", weight)
	for _, e := range mst {
		fmt.Printf(" %d-%d ($%d)\n", e.From, e.To, e.Weight)
	}
	// total cost: 16
	// 1-2 ($1)
	// 1-3 ($2)
	// 0-2 ($3)
	// 3-4 ($5)
	// 3-5 ($7)
}

The early break on len(mst) == numVertices-1 matters for dense graphs: after the MST is complete, the remaining majority of sorted edges are checked only if you forget to stop. When E is much larger than V, skipping that break wastes most of the runtime. Another common mistake is sorting the caller’s slice in place. The copy above keeps the input intact, which matters when the same edge list feeds multiple runs or is reused across requests.

Weight type is the third pitfall. The example uses int, which is fine for unit costs. Production code handling distances from a sensor mesh should use float64 or a fixed-point scale to avoid truncation, and large per-edge weights summed across millions of edges can overflow a 32-bit accumulator, so use int64 for the total on large graphs.

Visualizing Kruskal’s Algorithm: From Edges to MST

Visualization confirms correctness in a way that a passing unit test does not: you can watch components merge one edge at a time and observe which edges get rejected. The process is consistent: sort edges, then for each edge run the union-find membership check before accepting it into the tree.

The GraphWizard library for Go provides graph algorithms through a consistent API built on gonum’s graph interfaces, which makes it practical to render intermediate states. Go’s gonum/graph package supplies the underlying graph types. If you prefer not to maintain your own implementation, gonum includes prebuilt MST routines. The trade-off is that gonum’s generic graph interfaces add iterator indirection: a hand-rolled union-find and a flat edge slice often runs faster than the generic version for a single known graph type. The gonum repo, verified at github.com/gonum/gonum, had 8,427 stars and 580 forks as of September 2026.

For a reference implementation to compare with your own, TheAlgorithms/Go includes a Kruskal implementation, and that repo had 18,208 stars as of September 2026. Comparing your union-find against a known-good one is the fastest way to catch a subtle bug in the rank update.

Limitations and When to Use Kruskal’s Instead of Prim’s

Kruskal’s advantages come from its structure. Because it works on a global edge list, it needs no adjacency structure and no seed vertex, and it handles disconnected graphs without changes by producing a spanning forest. You detect the split afterward by checking whether the accepted edge count reached V-1. Prim’s loop finishes after visiting one component and returns an incomplete tree unless you restart it from an unvisited vertex.

The limitations are clear. The ACTE DAA guide lists Kruskal’s limitations as a poor fit for dense graphs, the mandatory full sort before processing, and non-adaptive behavior. On a complete graph, Kruskal’s O(E) edge storage becomes O(V^2), so the edge list itself can use more memory than the sort step. For dense inputs, Prim’s array variant avoids creating that list entirely. If your edge list is already ordered by weight, which happens when weights are timestamps or pre-existing cost tiers, Kruskal’s sort becomes a no-op you can skip, reducing it to near-linear union-find work.

Optimizing Kruskal’s for Large Graphs in Go

Three changes improve performance on large inputs. First, pre-allocate the union-find arrays and the MST slice to their final size so the runtime never grows them during the loop. Second, prefer path halving over recursive path compression to keep the find loop iterative and avoid call overhead on the hot path. Third, sort a copy rather than the caller’s slice, and reuse a single scratch buffer across runs instead of allocating a new one each time.

Note: The following code is an illustrative example and has not been verified against official documentation. Please refer to the official docs for production-ready code.

// Reuse one scratch buffer across many Kruskal runs to avoid
// re-allocating the sorted edge slice on every call.
type Solver struct {
	scratch []Edge
	dsu *DSU
}

func NewSolver(numVertices, maxEdges int) *Solver {
	return &Solver{
		scratch: make([]Edge, 0, maxEdges),
		dsu: NewDSU(numVertices),
	}
}

// Note: production use should reset the DSU between runs instead of
// reallocating, and should bound maxEdges to avoid unbounded growth
// if the input size is attacker-controlled.
func (s *Solver) Solve(numVertices int, edges []Edge) int {
	s.scratch = append(s.scratch[:0], edges...)
	sort.Slice(s.scratch, func(i, j int) bool {
		return s.scratch[i].Weight < s.scratch[j].Weight
	})
	total, used := 0, 0
	for _, e := range s.scratch {
		if s.dsu.Union(e.From, e.To) {
			total += e.Weight
			if used++; used == numVertices-1 {
				break
			}
		}
	}
	return total
}

Go’s sort is already parallel-capable in the standard library for sort.Slice on large slices, so hand-rolling a concurrent sort of edges rarely beats it. The bigger gain is avoiding allocation churn: at millions of edges, repeatedly allocating and discarding the sorted slice causes GC pressure in a profile long before the sort itself does. The union-find operations with path compression and union by rank keep near-constant amortized time, which makes the per-edge work small compared to the sort.

Summary: Choosing the Right MST Algorithm in Go

Kruskal’s algorithm is a practical first choice for sparse graphs, pre-sorted edge lists, and disconnected inputs where a spanning forest is acceptable. Its implementation is short, it needs no adjacency structure, and its union-find cycle check keeps per-edge work effectively constant. Prim’s algorithm performs better on dense graphs and adjacency-matrix inputs, where its array variant stays at O(V^2) and avoids building a quadratic edge list.

Key Takeaways:

Kruskal runs in O(E log E) always; the edge sort dominates, and union-find with path compression plus union by rank keeps cycle avoidance effectively constant per edge.

Prim with a binary heap runs in O(E log V), with the complexity depending on E; the array variant runs in O(V^2) and wins on dense inputs.

Break out of Kruskal’s loop at V-1 accepted edges or you waste runtime scanning the sorted remainder on dense graphs.

Kruskal handles disconnected graphs for free by producing a spanning forest; Prim needs an outer restart loop.

Benchmark on your own hardware with go test -bench=. -benchmem before committing to either, since constant factors decide the winner when the asymptotic bounds come close.

For more on how this comparison fits with other algorithm trade-offs in Go, see our earlier KMP vs Boyer-Moore comparison, which uses the same density-and-constant-factor reasoning for choosing between two correct algorithms.

Sources and References

Sources cited while researching and writing this article: