Minimum Spanning Tree

🌳 Building the Best Roads: Minimum Spanning Trees

Imagine you’re the mayor of a town with many villages. You want to connect ALL villages with roads, but you have a limited budget. How do you spend the LEAST money while making sure everyone is connected?

That’s exactly what a Minimum Spanning Tree (MST) does!

🏘️ The Story: Connecting Villages

Picture 5 villages on a map. Between each pair of villages, there’s a possible road with a cost to build it. Your job? Connect all villages using the cheapest total road cost - but here’s the rule: no circular roads (that wastes money!).

graph TD
    A["Village A"] -->|$4| B["Village B"]
    A -->|$2| C["Village C"]
    B -->|$1| C
    B -->|$5| D["Village D"]
    C -->|$3| D
    D -->|$6| E["Village E"]
    C -->|$4| E

The Minimum Spanning Tree finds the magic combination that:

• ✅ Connects EVERY village
• ✅ Uses the LEAST total cost
• ✅ Has NO circular paths (loops)

🧠 Two Heroes: Prim & Kruskal

Think of two different builders who solve this problem their own way:

Both builders end up with the SAME cheapest road network!

🌱 Prim’s Algorithm: Growing a Tree

The Simple Idea

Imagine planting a tree seed in one village. The tree grows by always reaching toward the nearest unconnected village.

Step by Step

1. Pick any starting village - this is your “tree”
2. Look at all roads leading from your tree to villages NOT in your tree
3. Pick the CHEAPEST road and add that village to your tree
4. Repeat until all villages are in your tree!

🎮 Let’s Play It Out!

Starting from Village A with this graph:

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

Round 1: Tree = {A}

• Options: A→B ($4), A→C ($2)
• Pick cheapest: A→C ($2) ✅
• Tree = {A, C}

Round 2: Tree = {A, C}

• Options: A→B ($4), C→D ($3)
• Pick cheapest: C→D ($3) ✅
• Tree = {A, C, D}

Round 3: Tree = {A, C, D}

• Options: A→B ($4), D→B ($1)
• Pick cheapest: D→B ($1) ✅
• Tree = {A, C, D, B} - ALL CONNECTED!

Total Cost: $2 + $3 + $1 = $6 🎉

Java Code (Simple Version)

// Prim's Algorithm - Simple Version
int[] minCost = new int[n]; // Cost to reach each village
boolean[] inTree = new boolean[n];
Arrays.fill(minCost, Integer.MAX_VALUE);
minCost[0] = 0; // Start from village 0

for (int count = 0; count < n; count++) {
    // Find cheapest village not in tree
    int u = -1;
    for (int v = 0; v < n; v++) {
        if (!inTree[v] &&
            (u == -1 || minCost[v] < minCost[u]))
            u = v;
    }
    inTree[u] = true;

    // Update costs to neighbors
    for (Edge e : graph[u]) {
        if (!inTree[e.to] && e.cost < minCost[e.to])
            minCost[e.to] = e.cost;
    }
}

⏱️ Speed Check

Tip: Use Priority Queue version for big graphs!

⚔️ Kruskal’s Algorithm: Sorting & Picking

The Simple Idea

Imagine you have a deck of cards. Each card is a road with its cost written on it. You sort all cards from cheapest to most expensive. Then, you pick cards one by one - but ONLY if it doesn’t create a circle!

Step by Step

1. Sort ALL roads from cheapest to most expensive
2. Pick the cheapest road that doesn’t create a loop
3. Repeat until you have (n-1) roads for n villages

🎮 Let’s Play It Out!

Roads sorted by cost:

1. B-D: $1
2. A-C: $2
3. C-D: $3
4. A-B: $4

Round 1: Pick B-D ($1) ✅ No loop! Round 2: Pick A-C ($2) ✅ No loop! Round 3: Pick C-D ($3) ✅ No loop! Now A-C-D-B connected! Round 4: Skip A-B ($4) ❌ Would create A-B-D-C-A loop!

Total Cost: $1 + $2 + $3 = $6 🎉

Same answer as Prim’s! Magic? No - just math! 🧙‍♂️

But Wait… How Do We Know If Something Creates a Loop?

This is where Union-Find becomes our superpower!

🔗 Union-Find: The Loop Detector

The Problem

When Kruskal picks a road A→B, he needs to know:

“Are A and B already connected through other roads?”

If yes → Adding this road creates a loop! ❌ If no → Safe to add! ✅

The Brilliant Idea: Families

Think of it like family groups:

• At first, every village is its own family (alone)
• When you connect two villages, their families merge
• Two villages in the SAME family = already connected!

🎮 Visual Example

Start: Each alone
[A] [B] [C] [D] [E]

Add edge A-C:
[A,C] [B] [D] [E]  // A and C are now family!

Add edge B-D:
[A,C] [B,D] [E]    // B and D are now family!

Add edge C-D:
[A,C,B,D] [E]      // Families merge!

Now if we try A-B:
A and B same family? YES!
→ LOOP! Don't add!

Two Operations

Basic Java Code

int[] parent = new int[n];

// Everyone starts as their own parent
for (int i = 0; i < n; i++)
    parent[i] = i;

// FIND: Who is my ultimate leader?
int find(int x) {
    while (parent[x] != x)
        x = parent[x];
    return x;
}

// UNION: Merge two families
void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    parent[rootX] = rootY;
}

// Same family? (Loop check!)
boolean connected(int x, int y) {
    return find(x) == find(y);
}

🚀 Union-Find Optimizations

The basic version works, but can be SLOW with long chains. Imagine finding your great-great-great-grandparent every time!

Optimization 1: Path Compression

Problem: Long chains make FIND slow

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

Solution: When finding root, make everyone point DIRECTLY to root!

After finding A:
A → E
B → E
C → E
D → E

Next time = 1 step only!

Java Code with Path Compression

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]); // Magic line!
    return parent[x];
}

Optimization 2: Union by Rank

Problem: Merging can create tall trees

Solution: Always attach the SHORTER tree under the TALLER tree!

Rank = height of tree

Before union(A, B):
Tree A (rank 3)    Tree B (rank 1)
    A                   B
   /|\
  ...

After: Attach B under A (not A under B!)

Java Code with Both Optimizations

int[] parent = new int[n];
int[] rank = new int[n];

// Initialize
for (int i = 0; i < n; i++) {
    parent[i] = i;
    rank[i] = 0;
}

// FIND with path compression
int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

// UNION by rank
void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if (rootX == rootY) return;

    // Attach smaller tree under bigger
    if (rank[rootX] < rank[rootY])
        parent[rootX] = rootY;
    else if (rank[rootX] > rank[rootY])
        parent[rootY] = rootX;
    else {
        parent[rootY] = rootX;
        rank[rootX]++;
    }
}

⚡ Speed Comparison

The technical term is O(α(n)) where α is the inverse Ackermann function - basically constant time for any realistic input! 🤯

🏗️ Kruskal’s Complete Code

Now we can write the full algorithm!

class Edge implements Comparable<Edge> {
    int from, to, cost;

    public int compareTo(Edge other) {
        return this.cost - other.cost;
    }
}

int kruskal(List<Edge> edges, int n) {
    Collections.sort(edges); // Sort by cost

    // Union-Find setup
    int[] parent = new int[n];
    int[] rank = new int[n];
    for (int i = 0; i < n; i++)
        parent[i] = i;

    int totalCost = 0;
    int edgesUsed = 0;

    for (Edge e : edges) {
        int rootA = find(e.from);
        int rootB = find(e.to);

        if (rootA != rootB) { // No loop!
            union(rootA, rootB);
            totalCost += e.cost;
            edgesUsed++;

            if (edgesUsed == n - 1)
                break; // Done!
        }
    }

    return totalCost;
}

🎯 When to Use Which?

graph TD
    A["Need MST?"] --> B{Dense Graph?}
    B -->|Many edges| C["Use Prim's]
    B -->|Few edges| D[Use Kruskal's"]
    C --> E["With Priority Queue"]
    D --> F["With Union-Find"]

🎓 Key Takeaways

1. MST = Connect all nodes with minimum total edge weight, no cycles

2. Prim’s = “Grow from one node” - pick cheapest edge to new node

3. Kruskal’s = “Sort & pick” - choose cheapest edges that don’t create loops

4. Union-Find = Fast way to check if two nodes are already connected

5. Path Compression + Union by Rank = Makes Union-Find blazingly fast!

🧠 Remember This!

Prim thinks LOCAL: “What’s the cheapest way to grow MY tree?”

Kruskal thinks GLOBAL: “What’s the cheapest edge in the WHOLE graph that’s still safe?”

Both find the same answer - the Minimum Spanning Tree! 🌳✨