Kruskal’s Algorithm — Connect the Dots, But Keep It Cheap

Let’s say you want to build bridges between islands 🏝️, and your goal is to connect all of them with the least cost, without making a circular path.

That’s exactly what Kruskal’s Algorithm does! It builds a Minimum Spanning Tree (MST) by always picking the cheapest available connection, but with a rule — no cycles allowed.

---

🧩 The Core Idea

Kruskal says: "Let’s sort all the edges by cost. Then, keep picking the cheapest edge that doesn’t form a loop — until everyone is connected."

---

🛠️ Step-by-Step

1. Sort all edges by their weights (lowest to highest).

2. Start with no connections (each node is its own island).

3. Pick the smallest edge.

   • If it connects two different groups, accept it.

   • If it forms a cycle, skip it.

4. Keep adding edges until all nodes are connected.

---

🎯 Real-Life Analogy

Think of islands connected by ropes.You have a bunch of ropes of different lengths.Your goal: tie all islands together using minimum rope, and no loops — because loops are just wasted rope.

---

📦 Where Is It Used?

• Designing road or electrical networks

• Laying out computer networks

• Clustering data

---

🧪 Quick Example

A --1-- B

|      |

4      2

|      |

C --3-- D

---

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

• Add A-B → ✅

• Add B-D → ✅

• Add C-D → ✅

• Skip A-C → ❌ (would make a cycle)

Total cost = 1 + 2 + 3 = 6

Boom! All connected, no waste. That’s Kruskal.

---

🤔 Kruskal vs Prim?

• Prim grows one tree step-by-step.

• Kruskal picks edges freely and merges trees carefully.

---

✅ Final Thought

Kruskal is like a bargain hunter 🛒 — always picks the cheapest item on the list, but smart enough not to buy something twice.