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.

Practice

1. What is the main goal of Kruskal's Algorithm in graph theory?

easy

A. To find the minimum spanning tree of a connected weighted graph

B. To find the shortest path between two nodes

C. To detect cycles in a graph

D. To sort the vertices of a graph

Solution

1. Step 1: Understand the purpose of Kruskal's Algorithm

   Kruskal's Algorithm is designed to find a subset of edges that connects all vertices with the minimum total edge weight and no cycles.

2. Step 2: Compare with other graph algorithms

   Unlike shortest path or cycle detection algorithms, Kruskal's focuses on building a minimum spanning tree.

3. Final Answer:

   To find the minimum spanning tree of a connected weighted graph -> Option A

4. Quick Check:

   Minimum Spanning Tree = Find minimum edges connecting all nodes [OK]

Hint: Kruskal connects all nodes with least total edge weight [OK]

Common Mistakes:

• Confusing MST with shortest path
• Thinking it detects cycles only
• Assuming it sorts vertices

2. Which of the following TypeScript code snippets correctly initializes the edges array for Kruskal's Algorithm?

easy

A. const edges: number[][] = [0, 1, 10, 1, 2, 5, 0, 2, 15];

B. const edges = {0:1:10, 1:2:5, 0:2:15};

C. const edges: [number, number, number][] = [[0, 1, 10], [1, 2, 5], [0, 2, 15]];

D. const edges: Array<number> = [[0, 1, 10], [1, 2, 5], [0, 2, 15]];

Solution

1. Step 1: Check the correct TypeScript tuple array syntax

   Edges should be an array of tuples, each tuple having three numbers: [node1, node2, weight]. const edges: [number, number, number][] = [[0, 1, 10], [1, 2, 5], [0, 2, 15]]; uses this syntax correctly.

2. Step 2: Identify incorrect syntax in other options

   const edges = {0:1:10, 1:2:5, 0:2:15}; uses invalid object syntax. const edges: number[][] = [0, 1, 10, 1, 2, 5, 0, 2, 15]; is a flat array, not an array of tuples. const edges: Array<number> = [[0, 1, 10], [1, 2, 5], [0, 2, 15]]; uses wrong type annotation (Array<number> instead of tuple array).

3. Final Answer:

   const edges: [number, number, number][] = [[0, 1, 10], [1, 2, 5], [0, 2, 15]]; -> Option C

4. Quick Check:

   Tuple array syntax = const edges: [number, number, number][] = [[0, 1, 10], [1, 2, 5], [0, 2, 15]]; [OK]

Hint: Use tuple arrays for edges: [node1, node2, weight][] [OK]

Common Mistakes:

• Using flat arrays instead of tuples
• Wrong object syntax for edges
• Incorrect type annotations

3. What will be the output edges of the minimum spanning tree after running Kruskal's Algorithm on this graph?

const edges: [number, number, number][] = [[0, 1, 4], [0, 2, 3], [1, 2, 1], [1, 3, 2], [2, 3, 4], [3, 4, 2], [4, 5, 6]];

medium

A. [[0, 1, 4], [1, 3, 2], [3, 4, 2], [4, 5, 6]]

B. [[1, 2, 1], [1, 3, 2], [3, 4, 2], [0, 2, 3], [4, 5, 6]]

C. [[1, 2, 1], [0, 2, 3], [1, 3, 2], [3, 4, 2]]

D. [[0, 1, 4], [0, 2, 3], [1, 2, 1], [4, 5, 6]]

Solution

1. Step 1: Sort edges by weight

   Sorted edges: [1,2,1], [1,3,2], [3,4,2], [0,2,3], [0,1,4], [2,3,4], [4,5,6]

2. Step 2: Pick edges without forming cycles until all nodes connected

   Pick [1,2,1], [1,3,2], [3,4,2], [0,2,3], and [4,5,6]. These connect all nodes with minimum total weight without cycles.

3. Final Answer:

   [[1, 2, 1], [1, 3, 2], [3, 4, 2], [0, 2, 3], [4, 5, 6]] -> Option B

4. Quick Check:

   Edges sorted + no cycles = [[1, 2, 1], [1, 3, 2], [3, 4, 2], [0, 2, 3], [4, 5, 6]] [OK]

Hint: Sort edges by weight, pick smallest without cycles [OK]

Common Mistakes:

• Choosing heavier edges first
• Including edges that form cycles
• Missing edges to connect all nodes

4. Identify the error in this TypeScript snippet implementing Kruskal's Algorithm:

const edges: [number, number, number][] = [[0,1,1],[1,2,2],[0,2,3]];
const parent = [0,1,2];
function find(x: number): number {
  if(parent[x] === x) return x;
  return find(parent[x]);
}
function union(a: number, b: number) {
  const rootA = find(a);
  const rootB = find(b);
  if(rootA !== rootB) parent[rootB] = rootA;
}
// Missing sorting of edges before processing

medium

A. The union function incorrectly assigns parent

B. The find function does not implement path compression

C. The parent array should be initialized with -1

D. The edges array is not sorted by weight before processing

Solution

1. Step 1: Check Kruskal's Algorithm requirements

   Kruskal's requires edges to be sorted by weight ascending before union-find operations.

2. Step 2: Identify missing sorting step

   The code comment notes missing sorting; without sorting, MST may not be minimal.

3. Final Answer:

   The edges array is not sorted by weight before processing -> Option D

4. Quick Check:

   Sorting edges first is essential [OK]

Hint: Always sort edges by weight before union-find steps [OK]

Common Mistakes:

• Skipping edge sorting
• Ignoring path compression (optional)
• Incorrect parent initialization

5. Given a graph with vertices 0 to 4 and edges:

[[0,1,10],[0,2,6],[0,3,5],[1,3,15],[2,3,4]]

Use Kruskal's Algorithm to find the total weight of the minimum spanning tree.

hard

A. 19

B. 20

C. 25

D. 15

Solution

1. Step 1: Sort edges by weight

   Sorted edges: [2,3,4], [0,3,5], [0,2,6], [0,1,10], [1,3,15]

2. Step 2: Pick edges without cycles until all vertices connected

   Pick [2,3,4], [0,3,5], [0,2,6] connect nodes 0,2,3. Then pick [0,1,10] to connect node 1. Total weight = 4+5+6+10 = 25. But this forms a cycle because 0,2,3 are connected. Instead, pick [2,3,4], [0,3,5], [0,1,10]. Then pick [0,2,6] creates cycle. So skip [0,2,6]. Next pick [1,3,15] is heavier and unnecessary. So MST edges: [2,3,4], [0,3,5], [0,1,10]. Total weight = 4+5+10=19.

3. Final Answer:

   19 -> Option A

4. Quick Check:

   Sum of MST edges weights = 19 [OK]

Hint: Sort edges, pick smallest without cycles, sum weights [OK]

Common Mistakes:

• Including edges that form cycles
• Adding all edges without checking
• Misordering edges by weight