Minimum Spanning Tree Kruskal's Algorithm in DSA Typescript

Mental Model

Pick the shortest edges one by one without making loops until all points connect.

Analogy: Imagine building roads between cities. You want to connect all cities with the least total road length, but never build a road that creates a circle of roads.

Graph:
  A---2---B
  |       |
  3       1
  |       |
  C---4---D

Edges with weights:
  A-B:2, B-D:1, A-C:3, C-D:4

Goal: Connect all nodes with minimum total weight without loops.

Dry Run Walkthrough

Input: Graph with nodes A, B, C, D and edges: A-B(2), B-D(1), A-C(3), C-D(4)

Goal: Find the minimum spanning tree connecting all nodes with minimum total edge weight and no cycles.

Step 1: Sort edges by weight: B-D(1), A-B(2), A-C(3), C-D(4)

Edges sorted: [B-D(1), A-B(2), A-C(3), C-D(4)]

Why: We pick edges from smallest to largest to minimize total weight.

Step 2: Pick edge B-D(1), add to MST since it connects two different sets

MST edges: B-D(1)
Sets: {A}, {B, D}, {C}

Why: No cycle formed, so we add the smallest edge.

Step 3: Pick edge A-B(2), add to MST since A and B are in different sets

MST edges: B-D(1), A-B(2)
Sets: {A, B, D}, {C}

Why: Connecting A to B-D group without cycle.

Step 4: Pick edge A-C(3), add to MST since C is separate

MST edges: B-D(1), A-B(2), A-C(3)
Sets: {A, B, C, D}

Why: All nodes connected, MST complete.

Step 5: Skip edge C-D(4) because it connects nodes already in the same set (would form cycle)

MST edges unchanged: B-D(1), A-B(2), A-C(3)

Why: Avoid cycles to keep MST valid.

Result:

MST edges: B-D(1) -> A-B(2) -> A-C(3)
Total weight: 6

Annotated Code

DSA Typescript

class DisjointSet {
  parent: number[];
  rank: number[];

  constructor(n: number) {
    this.parent = Array(n).fill(0).map((_, i) => i);
    this.rank = Array(n).fill(0);
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // path compression
    }
    return this.parent[x];
  }

  union(x: number, y: number): boolean {
    let rootX = this.find(x);
    let rootY = this.find(y);
    if (rootX === rootY) return false; // cycle detected

    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
    return true;
  }
}

interface Edge {
  from: number;
  to: number;
  weight: number;
}

function kruskalMST(nodesCount: number, edges: Edge[]): Edge[] {
  edges.sort((a, b) => a.weight - b.weight); // sort edges by weight
  const ds = new DisjointSet(nodesCount);
  const mst: Edge[] = [];

  for (const edge of edges) {
    if (ds.union(edge.from, edge.to)) {
      mst.push(edge); // add edge if no cycle
    }
  }
  return mst;
}

// Driver code
// Map nodes A=0, B=1, C=2, D=3
const edges: Edge[] = [
  { from: 0, to: 1, weight: 2 }, // A-B
  { from: 1, to: 3, weight: 1 }, // B-D
  { from: 0, to: 2, weight: 3 }, // A-C
  { from: 2, to: 3, weight: 4 }  // C-D
];

const mst = kruskalMST(4, edges);

for (const e of mst) {
  console.log(`Edge from ${String.fromCharCode(65 + e.from)} to ${String.fromCharCode(65 + e.to)} with weight ${e.weight}`);
}

edges.sort((a, b) => a.weight - b.weight);

Sort edges by weight ascending to pick smallest edges first

if (ds.union(edge.from, edge.to)) {

Add edge only if it connects two different sets (no cycle)

this.parent[x] = this.find(this.parent[x]);

Path compression to speed up find operation

Output

Edge from B to D with weight 1

Edge from A to B with weight 2

Edge from A to C with weight 3

Complexity Analysis

Time: O(E log E) because sorting edges dominates and union-find operations are almost O(1)

Space: O(V) for disjoint set arrays storing parent and rank for each node

vs Alternative: Compared to Prim's algorithm which uses priority queues, Kruskal is simpler for sparse graphs and edges sorted upfront

Edge Cases

Empty graph with no edges

Returns empty MST since no edges to connect nodes

DSA Typescript

edges.sort((a, b) => a.weight - b.weight);

Graph with single node and no edges

Returns empty MST as no edges exist

DSA Typescript

edges.sort((a, b) => a.weight - b.weight);

Graph with multiple edges having same weight

Algorithm picks edges in sorted order and union-find prevents cycles correctly

DSA Typescript

if (ds.union(edge.from, edge.to)) {

When to Use This Pattern

When you need to connect all points with minimum total cost and avoid cycles, use Kruskal's MST with edge sorting and union-find to detect cycles.

Common Mistakes

Mistake: Not sorting edges by weight before processing
Fix: Sort edges ascending by weight before starting union-find steps

Mistake: Not using union-find or cycle detection, causing cycles in MST
Fix: Use union-find to check if adding an edge creates a cycle before adding it

Summary

Builds a minimum spanning tree by adding edges from smallest to largest without cycles.

Use when you want the cheapest way to connect all nodes in a graph.

Sorting edges and using union-find to avoid cycles is the key insight.