Minimum Spanning Tree Kruskal's Algorithm in DSA Javascript

Mental Model

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

Analogy: Imagine connecting houses with roads. You want to use the cheapest roads but still connect every house without making any circle paths.

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

Dry Run Walkthrough

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

Goal: Find the cheapest set of edges that connect all points without any loops

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

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

Why: We pick edges from smallest to largest to keep total cost low

Step 2: Pick edge A-C(1), add it to MST

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

Why: First smallest edge connects two points without loop

Step 3: Pick edge A-B(2), add it to MST

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

Why: Connect B to existing set without loop

Step 4: Check edge B-C(3), skip because it forms a loop in {A, B, C}

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

Why: Adding B-C would create a cycle, so skip

Step 5: Pick edge C-D(4), add it to MST

MST edges: A-C(1), A-B(2), C-D(4)
Connected sets: {A, B, C, D}

Why: Connect last point D without cycle

Step 6: Skip edge B-D(5) because all points connected

MST edges: A-C(1), A-B(2), C-D(4)
Connected sets: {A, B, C, D}

Why: No need to add more edges once all points connected

Result:

MST edges: A-C(1) -> A-B(2) -> C-D(4)
All points connected with minimum total cost 7

Annotated Code

DSA Javascript

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

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

  union(x, y) {
    let rootX = this.find(x);
    let rootY = this.find(y);
    if (rootX === rootY) return false; // already connected
    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;
  }
}

function kruskalMST(vertices, edges) {
  edges.sort((a, b) => a.weight - b.weight); // sort edges by weight
  const ds = new DisjointSet(vertices.length);
  const mst = [];
  for (const edge of edges) {
    if (ds.union(edge.u, edge.v)) { // if union succeeds, add edge
      mst.push(edge);
    }
  }
  return mst;
}

// Map points to indices: A=0, B=1, C=2, D=3
const vertices = ["A", "B", "C", "D"];
const edges = [
  { u: 0, v: 2, weight: 1 }, // A-C
  { u: 0, v: 1, weight: 2 }, // A-B
  { u: 1, v: 2, weight: 3 }, // B-C
  { u: 2, v: 3, weight: 4 }, // C-D
  { u: 1, v: 3, weight: 5 }  // B-D
];

const mst = kruskalMST(vertices, edges);
for (const edge of mst) {
  console.log(`${vertices[edge.u]} - ${vertices[edge.v]} : ${edge.weight}`);
}

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

sort edges by weight ascending to pick smallest first

if (ds.union(edge.u, edge.v)) {

try to connect two points; only add edge if no cycle formed

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

path compression to speed up future find operations

return false; // already connected

skip edge if it connects points already in same set (cycle)

Output

A - C : 1

A - B : 2

C - D : 4

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 vertex

vs Alternative: Compared to Prim's algorithm which uses priority queue and adjacency list, Kruskal is simpler for sparse graphs but sorting edges can be costly for dense graphs

Edge Cases

Empty graph with no edges

Returns empty MST since no edges to connect points

DSA Javascript

for (const edge of edges) { if (ds.union(edge.u, edge.v)) {

Graph with single vertex and no edges

Returns empty MST as no edges exist

DSA Javascript

for (const edge of edges) { if (ds.union(edge.u, edge.v)) {

Graph with multiple edges having same weight

Algorithm picks edges in sorted order; ties resolved by order in input

DSA Javascript

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

When to Use This Pattern

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

Common Mistakes

Mistake: Not checking if adding an edge creates a cycle, causing wrong MST
Fix: Use union-find to check if two points are already connected before adding edge

Mistake: Sorting edges incorrectly or not sorting at all
Fix: Always sort edges by weight ascending before processing

Summary

Finds the cheapest way to connect all points without loops by picking smallest edges first.

Use when you have a list of edges and want to build a minimum cost network connecting all nodes.

Sort edges by weight and use union-find to avoid cycles while building MST.

Practice

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

easy

A. To find the minimum spanning tree of a 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 Kruskal's Algorithm purpose

   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 problems

   Shortest path and cycle detection are different problems solved by other algorithms like Dijkstra or DFS, not Kruskal's.

3. Final Answer:

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

4. Quick Check:

   Minimum Spanning Tree = Kruskal's Algorithm goal [OK]

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

Common Mistakes:

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

2. Which of the following is the correct way to sort edges by weight in JavaScript for Kruskal's Algorithm?

easy

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

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

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

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

Solution

1. Step 1: Understand sorting for MST

   Kruskal's Algorithm requires edges sorted in ascending order by weight to pick smallest edges first.

2. Step 2: Check JavaScript sort syntax

   Using edges.sort((a, b) => a.weight - b.weight); sorts edges from smallest to largest weight correctly.

3. Final Answer:

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

4. Quick Check:

   Sort ascending by weight = edges.sort((a, b) => a.weight - b.weight); [OK]

Hint: Sort edges ascending by weight using (a,b) => a.weight - b.weight [OK]

Common Mistakes:

• Sorting descending instead of ascending
• Using addition or multiplication in sort callback
• Not returning a number in sort function

3. Consider the following edges of a graph:
const edges = [ {from: 'A', to: 'B', weight: 1}, {from: 'B', to: 'C', weight: 4}, {from: 'A', to: 'C', weight: 3}, {from: 'C', to: 'D', weight: 2} ];
After applying Kruskal's Algorithm, which edges will be included in the MST?

medium

A. [{A-B,1}, {A-C,3}, {B-C,4}]

B. [{A-B,1}, {C-D,2}, {A-C,3}]

C. [{A-B,1}, {C-D,2}, {B-C,4}]

D. [{B-C,4}, {A-C,3}, {C-D,2}]

Solution

1. Step 1: Sort edges by weight ascending

   Sorted edges: (A-B,1), (C-D,2), (A-C,3), (B-C,4)

2. Step 2: Pick edges without forming cycles

   Pick A-B (1), then C-D (2), then A-C (3). Adding B-C (4) would form a cycle, so skip it.

3. Final Answer:

   [{A-B,1}, {C-D,2}, {A-C,3}] -> Option B

4. Quick Check:

   Edges with smallest weights and no cycles = [{A-B,1}, {C-D,2}, {A-C,3}] [OK]

Hint: Pick edges ascending weight, skip if cycle forms [OK]

Common Mistakes:

• Including edges that form cycles
• Not sorting edges before selection
• Choosing heavier edges unnecessarily

4. The following code snippet tries to implement Kruskal's Algorithm but has a bug:

const edges = [
  {from: 'A', to: 'B', weight: 1},
  {from: 'B', to: 'C', weight: 2},
  {from: 'A', to: 'C', weight: 3}
];

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

const mst = [];
const visited = new Set();

for (const edge of edges) {
  if (!visited.has(edge.from) || !visited.has(edge.to)) {
    mst.push(edge);
    visited.add(edge.from);
    visited.add(edge.to);
  }
}
console.log(mst);

What is the main issue with this code?

medium

A. It does not correctly check for cycles, so MST may be incorrect

B. The edges are not sorted properly

C. The visited set is not initialized

D. It uses an array instead of a linked list for MST

Solution

1. Step 1: Analyze cycle detection logic

   The code uses a visited set to check if nodes are visited, but this does not detect cycles correctly in Kruskal's Algorithm.

2. Step 2: Understand correct cycle detection

   Kruskal's requires a Union-Find or Disjoint Set data structure to detect cycles properly, not just visited nodes.

3. Final Answer:

   It does not correctly check for cycles, so MST may be incorrect -> Option A

4. Quick Check:

   Cycle detection needs Union-Find, not visited set [OK]

Hint: Use Union-Find to detect cycles, not visited nodes [OK]

Common Mistakes:

• Using visited set for cycle detection
• Ignoring cycle checks
• Assuming sorting fixes all issues

5. You have a graph with vertices ['A', 'B', 'C', 'D', 'E'] and edges:

const edges = [
  {from: 'A', to: 'B', weight: 1},
  {from: 'B', to: 'C', weight: 3},
  {from: 'A', to: 'C', weight: 2},
  {from: 'C', to: 'D', weight: 4},
  {from: 'D', to: 'E', weight: 5},
  {from: 'B', to: 'E', weight: 6}
];

Using Kruskal's Algorithm with a Union-Find structure, what is the total weight of the minimum spanning tree?

hard

A. 10

B. 15

C. 12

D. 16

Solution

1. Step 1: Sort edges by weight ascending

   Sorted edges: (A-B,1), (A-C,2), (B-C,3), (C-D,4), (D-E,5), (B-E,6)

2. Step 2: Pick edges without cycles using Union-Find

   Pick A-B(1), A-C(2), B-C(3) forms cycle, skip B-C. Pick C-D(4), D-E(5). Total weight = 1+2+4+5 = 12.

3. Final Answer:

   12 -> Option C

4. Quick Check:

   Sum of MST edges = 12 [OK]

Hint: Sum smallest edges without cycles using Union-Find [OK]

Common Mistakes:

• Including edges that form cycles
• Adding all edges without checking
• Misordering edges before selection