Graphs

Graph Patterns: Minimum Spanning Tree (Kruskal's Algorithm)

May 2026
7 min read

While Prim's algorithm builds the MST outward from a single central node, Kruskal's algorithm takes a global view, sorting all edges and stitching them together.

Introduction

Kruskal’s algorithm is the second major way to construct a Minimum Spanning Tree. Unlike Prim's, which focuses on nodes, Kruskal's strictly focuses on edges.

The Mechanics

  1. Sort: We extract every single edge in the graph and sort them in ascending order based on their weight.
  2. Iterate: We loop through our sorted edge list, starting with the absolute cheapest edge in the entire graph.
  3. Union-Find: We use a Disjoint Set (Union-Find) to check if the two nodes connected by the edge are already in the same network.
    • If they are not connected, we merge them and add the edge's weight to our total.
    • If they are already connected, adding this edge would create a cycle, so we simply discard it and move on.

This algorithm is incredibly intuitive and is highly optimal for sparse graphs.

Implementation

java
class Solution { // Edge class implements Comparable for easy sorting static class Edge implements Comparable<Edge> { int u, v, weight; Edge(int u, int v, int weight) { this.u = u; this.v = v; this.weight = weight; } public int compareTo(Edge compareEdge) { return this.weight - compareEdge.weight; } } public int spanningTree(int V, ArrayList<Edge> edges) { // Sort all edges from smallest to largest Collections.sort(edges); UnionFind uf = new UnionFind(V); int mstCost = 0; for (Edge edge : edges) { // If uniting the nodes does NOT form a cycle if (uf.unite(edge.u, edge.v)) { mstCost += edge.weight; } } return mstCost; } }