Minimum Spanning Tree

🌳 Minimum Spanning Tree: Building the Cheapest Road Network

The Story Begins…

Imagine you’re the mayor of a brand new town! 🏘️ You have 5 villages scattered across your land, and you need to connect them all with roads. But here’s the catch: roads cost money to build, and you want to spend as little money as possible while making sure everyone can reach everyone else.

This is exactly what a Minimum Spanning Tree (MST) solves!

🤔 What is a Minimum Spanning Tree?

Think of it like connecting dots with the cheapest string possible.

Simple Rules:

• ✅ Every village must be reachable from any other village
• ✅ Use the least total road length (cost)
• ❌ No loops! (That’s wasted road)
• ❌ No extra roads (exactly enough to connect everyone)

Real Life Examples:

• 🔌 Electric company connecting houses with minimum wire
• 🌐 Internet cables between cities
• 💧 Water pipes in a neighborhood

graph TD
    A["Village A"] -->|Cost 2| B["Village B"]
    B -->|Cost 3| C["Village C"]
    A -->|Cost 4| C
    style A fill:#4ECDC4
    style B fill:#4ECDC4
    style C fill:#4ECDC4

The MST picks edges 2 + 3 = 5 (not 4 + 3 = 7 or 2 + 4 = 6)

🌟 Prim’s Algorithm: The Greedy Growing Tree

The Story

Imagine you’re building a tree fort and can only add one branch at a time. You always pick the shortest branch that connects to what you’ve already built!

How It Works (5 Simple Steps)

1. Start anywhere - Pick any village as your starting point
2. Look at your neighbors - See all roads going out from your tree
3. Pick the cheapest - Choose the road with the smallest cost
4. Add it to your tree - That village is now part of your group!
5. Repeat - Keep going until everyone is connected

Visual Example

Villages: A, B, C, D
Roads: A-B(1), A-C(4), B-C(2), B-D(5), C-D(3)

Step 1: Start at A
        Tree = {A}

Step 2: Cheapest edge from A?
        A-B costs 1 ← PICK THIS!
        A-C costs 4
        Tree = {A, B}

Step 3: Cheapest edge from A or B?
        A-C costs 4
        B-C costs 2 ← PICK THIS!
        B-D costs 5
        Tree = {A, B, C}

Step 4: Cheapest edge to new village?
        C-D costs 3 ← PICK THIS!
        Tree = {A, B, C, D}

DONE! Total cost: 1 + 2 + 3 = 6

JavaScript Code

function primsMST(graph, start) {
  const visited = new Set([start]);
  const mst = [];

  while (visited.size < graph.vertices) {
    let minEdge = null;
    let minCost = Infinity;

    // Check all edges from visited nodes
    for (const node of visited) {
      for (const [neighbor, cost] of graph[node]) {
        if (!visited.has(neighbor)) {
          if (cost < minCost) {
            minCost = cost;
            minEdge = { from: node, to: neighbor, cost };
          }
        }
      }
    }

    if (minEdge) {
      mst.push(minEdge);
      visited.add(minEdge.to);
    }
  }
  return mst;
}

Key Insight 💡

Prim’s is like growing a plant - you start from one seed and keep expanding outward, always choosing the shortest path to add a new leaf!

⚔️ Kruskal’s Algorithm: The Smart Road Builder

The Story

Imagine you have a list of all possible roads sorted by cost. You go through the list from cheapest to most expensive, building each road unless it creates a loop!

How It Works (4 Simple Steps)

1. Sort all edges - Put all roads in order (cheapest first)
2. Pick the cheapest - Take the first road from your list
3. Check for loops - Will this road create a circle?
   • If YES → Skip it! ❌
   • If NO → Build it! ✅
4. Repeat - Until you have (n-1) roads for n villages

Visual Example

Villages: A, B, C, D
All roads sorted: A-B(1), B-C(2), C-D(3), A-C(4), B-D(5)

Step 1: A-B costs 1
        Creates loop? NO → BUILD IT ✅

Step 2: B-C costs 2
        Creates loop? NO → BUILD IT ✅

Step 3: C-D costs 3
        Creates loop? NO → BUILD IT ✅

Step 4: A-C costs 4
        Creates loop? YES (A→B→C→A) → SKIP ❌

DONE! Total cost: 1 + 2 + 3 = 6

JavaScript Code

function kruskalsMST(edges, numVertices) {
  // Sort edges by cost
  edges.sort((a, b) => a.cost - b.cost);

  const uf = new UnionFind(numVertices);
  const mst = [];

  for (const edge of edges) {
    // If they're in different groups, connect them!
    if (uf.find(edge.from) !== uf.find(edge.to)) {
      mst.push(edge);
      uf.union(edge.from, edge.to);
    }

    // Stop when we have enough edges
    if (mst.length === numVertices - 1) break;
  }

  return mst;
}

Key Insight 💡

Kruskal’s is like sorting your Halloween candy and eating from best to worst, but skipping any candy that would give you a tummy ache (loops)!

🔗 Union-Find: The Group Tracker

The Big Question

How do we quickly check if two villages are already connected? That’s where Union-Find saves the day!

The Story

Imagine every village wears a colored hat. Villages in the same group wear the same color!

• Find: “What color hat does this village wear?”
• Union: “Let’s make these two groups wear the same color!”

Basic Version

class UnionFind {
  constructor(size) {
    // At first, everyone is their own group
    this.parent = Array.from({ length: size }, (_, i) => i);
  }

  // Find the leader of this person's group
  find(x) {
    if (this.parent[x] !== x) {
      return this.find(this.parent[x]);
    }
    return x;
  }

  // Merge two groups together
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) {
      this.parent[rootX] = rootY;
    }
  }
}

Visual Example

Before any roads:
A → A (leader)
B → B (leader)
C → C (leader)
D → D (leader)

Build road A-B:
A → B (now B is A's leader)
B → B (leader)
C → C (leader)
D → D (leader)

Build road B-C:
A → B → C (follow the chain!)
B → C
C → C (leader)
D → D (leader)

🚀 Union-Find Optimizations: Making It SUPER Fast!

The basic version works, but it can get slow. Imagine a really long chain of villages - finding the leader takes forever!

Optimization 1: Path Compression

The Problem: Long chains slow us down.

The Fix: When you find the leader, make EVERYONE point directly to them!

Before: A → B → C → D → E (leader)
        Finding A's leader = 4 steps 😓

After:  A → E
        B → E
        C → E
        D → E
        E → E (leader)
        Finding A's leader = 1 step 🚀

find(x) {
  if (this.parent[x] !== x) {
    // Magic line! Point directly to the root
    this.parent[x] = this.find(this.parent[x]);
  }
  return this.parent[x];
}

Optimization 2: Union by Rank

The Problem: Randomly merging creates unbalanced trees.

The Fix: Always attach the shorter tree under the taller tree!

Think of it like stacking boxes: put the smaller pile on top of the bigger pile, not the other way around!

class OptimizedUnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.rank = new Array(size).fill(0);
  }

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

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX === rootY) return;

    // Attach smaller tree under larger tree
    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]++;
    }
  }
}

Speed Comparison ⚡

The α(n) is the inverse Ackermann function - fancy math speak for “basically constant time”!

🆚 Prim’s vs Kruskal’s: When to Use Which?

Quick Rule:

• Many edges? → Prim’s 🌱
• Few edges? → Kruskal’s ⚔️

🎯 Summary: Your MST Toolkit

graph TD
    MST["Minimum Spanning Tree"]
    MST --> P["Prim's Algorithm]
    MST --> K[Kruskal's Algorithm"]
    K --> UF["Union-Find"]
    UF --> PC["Path Compression"]
    UF --> UR["Union by Rank"]

    style MST fill:#FF6B6B
    style P fill:#4ECDC4
    style K fill:#45B7D1
    style UF fill:#96CEB4
    style PC fill:#FFEAA7
    style UR fill:#FFEAA7

What You Learned Today 🏆

1. MST = Connect everything with minimum total cost
2. Prim’s = Grow from one point, always add cheapest neighbor
3. Kruskal’s = Sort all edges, add cheapest that doesn’t loop
4. Union-Find = Track who’s connected to whom
5. Path Compression = Make everyone point to the leader
6. Union by Rank = Keep trees balanced

🚀 You’re Ready!

You now understand how companies build networks, how cities plan roads, and how computer scientists connect things efficiently!

The next time you see power lines or internet cables, you’ll know: someone used an MST algorithm to save money! 💰

Go forth and build your minimum spanning trees! 🌳✨