Minimum Spanning Tree (MST)

Posted on by

🌐 What is a Spanning Tree?

Take a connected graph (a set of points joined by lines).
A spanning tree is:

  • A set of edges
  • That connects all vertices
  • With no cycles
  • And uses only the edges of the original graph

Think of it like placing just enough wires between rooms of a house so that electricity reaches everywhere, but you don’t waste wire on loops.

💰 So What Makes It “Minimum”?

A Minimum Spanning Tree (MST) is a spanning tree where the total weight (sum of edge costs) is as small as possible.

If weights represent:

  • distance → shortest cable length
  • cost → cheapest network
  • time → fastest connection

then MST helps you build the most efficient system.

🎯 A Simple Weighted Graph

Let’s take a small graph as an example:

      (2)
   A ------- B
   | \       |
 (3|  \5)   (1)
   |    \    |
   C ---- D
      (4)

Each number is a weight — think of it as kilometers, cost, or effort.

Your goal:
Pick a set of edges that connects A, B, C, and D, avoids loops, and keeps the total weight as low as possible.

🌳 An MST of the Above Graph

One possible MST for the graph looks like this:

      (2)
   A ------- B
   |
 (3|
   |
   C ------- D
        (4)

Selected edges: 2, 3, 4
Total weight = 2 + 3 + 4 = 9

Notice:

  • All nodes are connected
  • No cycles are formed
  • Total weight is minimal

🧠 How Do We Find an MST?

There are two famous methods, and both are surprisingly intuitive.

⭐ 1. Kruskal’s Algorithm — “Pick the cheapest first”

Kruskal feels like shopping during a sale.
You sort all edges from cheapest to costliest, and then:

  1. Pick the smallest edge.
  2. Add the next smallest edge.
  3. Skip an edge if it creates a cycle.
  4. Keep going until all vertices are connected.

Super simple idea: Buy the cheap stuff first, but don’t take duplicates.

⭐ 2. Prim’s Algorithm — “Grow like a tree”

Prim works like you’re slowly spreading out from one town.

  1. Start at any vertex.
  2. Choose the smallest edge that connects to a new vertex.
  3. Repeat — always attach the next nearest vertex.
  4. Stop when all vertices are included.

It’s like expanding a network step-by-step, always choosing the most affordable connection.

✨ Why Minimum Spanning Trees Matter

MSTs appear in many real-world problems:

  • Designing computer networks
  • Planning telecom towers
  • Laying railway tracks or roads
  • Electricity grid design
  • Clustering algorithms in machine learning
  • Social network analysis

Anywhere you want everything connected efficiently, MSTs are extremely helpful.