Graph Algorithms

Kruskal's Algorithm

What is a Minimum Spanning Tree?

A minimum spanning tree (MST) of a connected, undirected, weighted graph is a subset of its edges that connects every vertex together, contains no cycles, and has the smallest possible total edge weight among all such subsets. "Spanning" means every vertex is included; "tree" means there's exactly one path between any two vertices in it (n vertices, n-1 edges, no cycles); "minimum" means no other spanning tree costs less.

How Does Kruskal's Algorithm Work?

Kruskal's algorithm builds one with a simple greedy rule: sort every edge in the graph by weight, from cheapest to most expensive, then walk through them in that order, adding each edge to the tree unless doing so would create a cycle. An edge creates a cycle exactly when its two endpoints are already connected to each other through edges already accepted — so the only real question at each step is "are these two vertices already in the same connected piece?"

That question is answered efficiently with a Union-Find (disjoint-set) structure, which tracks which connected component each vertex currently belongs to. Checking whether two vertices are in the same component is a "find" operation; accepting an edge and merging two components is a "union" operation. Both run in close to constant time with the right implementation, which is what keeps the whole algorithm fast even though it needs one check per edge.

Cheapest edges are taken first; A-B and C-D are rejected since they'd close a cycle
12438ABCDsolid = in MST (total 6) · dashed = rejected (would cycle)

Algorithm Steps

  1. Sort all edges in the graph by weight, ascending
  2. Process edges in that order, and for each one:
    • If its two endpoints are in different components, accept the edge — add it to the tree and merge the two components
    • If its two endpoints are already in the same component, reject the edge — accepting it would create a cycle
  3. Stop once the tree has (number of vertices − 1) edges — every vertex is now connected

Time Complexity

  • Time Complexity: O(E log E) — dominated by sorting the edge list; the Union-Find operations that follow are nearly O(1) each.
  • Space Complexity: O(V + E) — for the edge list and the Union-Find structure.

Time Complexity Analysis

Advertisement

Kruskal's algorithm is the standard choice when a graph is sparse (relatively few edges compared to vertices) since sorting the edge list dominates its cost. It's used to design minimum-cost networks — laying cable or pipe to connect a set of locations as cheaply as possible, building efficient road or utility networks, and as a subroutine in clustering algorithms that group data points by cutting the most expensive edges out of a spanning tree.

Daily DSA Challenge by Scale Engineer

Build the cheapest possible tree connecting every vertex, by greedily accepting the smallest edge that doesn't form a cycle

Build a weighted graph and run Kruskal's algorithm

Graph

Add a vertex to begin
Vertex (color = component)Edge under considerationAccepted into MST

Test Your Knowledge before moving forward!

Kruskal's Algorithm Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Kruskal's Algorithm Implementation

// Union-Find (disjoint set): tracks which component each vertex belongs to.
function find(parent, v) {
  while (parent[v] !== v) v = parent[v];
  return v;
}

function union(parent, a, b) {
  parent[find(parent, a)] = find(parent, b);
}

// Process edges cheapest-first; only accept an edge if its endpoints are
// in different components -- accepting it otherwise would create a cycle.
function kruskal(vertices, edges) {
  const parent = {};
  vertices.forEach((v) => (parent[v] = v));

  const sorted = [...edges].sort((a, b) => a.weight - b.weight);
  const mst = [];
  let totalWeight = 0;

  for (const edge of sorted) {
    const rootA = find(parent, edge.from);
    const rootB = find(parent, edge.to);
    if (rootA !== rootB) {
      union(parent, rootA, rootB);
      mst.push(edge);
      totalWeight += edge.weight;
    }
  }

  return { mst, totalWeight };
}

// Usage example
const vertices = ["A", "B", "C", "D"];
const edges = [
  { from: "A", to: "B", weight: 4 },
  { from: "A", to: "C", weight: 1 },
  { from: "C", to: "B", weight: 2 },
  { from: "B", to: "D", weight: 5 },
  { from: "C", to: "D", weight: 8 },
];
kruskal(vertices, edges); // mst: A-C, C-B, B-D — totalWeight: 8

Done With the Learning

Mark Kruskal's Algorithm as done and view it on your dashboard

Explore Other Topics

Prim's Algorithm

Topological Sort

Dijkstra's Algorithm

Breadth-First Search

Depth-First Search

Adjacency List