Minimum Spanning Tree (MST)

Definition

A Minimum Spanning Tree is a subset of edges in a connected, weighted graph that connects all vertices together without any cycles and with the minimum total edge weight.

Real-World Analogy

Laying Internet Cables: You need to connect 5 office buildings with fiber optic cable. Digging paths costs money. You want to connect all buildings so everyone has internet, but you want to dig the least amount of distance possible. You don’t need loops (redundant paths); you just need everything connected.

Two Main Algorithms

1. Prim’s Algorithm:

• Start at one node.
• Grow the tree by always adding the cheapest edge that connects a node inside the tree to one outside.
• Similar to Dijkstra.

1. Kruskal’s Algorithm:

• Sort all edges by weight (smallest to largest).
• Iterate through sorted edges. Add the edge to the tree unless it creates a cycle.
• Uses Disjoint Set Union (DSU) to check for cycles.

Code Example (Kruskal’s Logic)

# Pseudo-code logic for understanding
def kruskal(edges, num_vertices):
    edges.sort() # Sort by weight
    mst = []
    dsu = DSU(num_vertices) # Helper class to track connections
   
    for weight, u, v in edges:
        # If u and v are NOT already connected
        if dsu.find(u) != dsu.find(v):
            dsu.union(u, v) # Connect them
            mst.append((u, v, weight))
           
    return mst

Use Cases

• Network Design: Telecommunication cables, electrical grids, water pipelines.
• Cluster Analysis: Grouping similar items in Machine Learning.