Minimum Spanning Tree (MST)

January 8, 2026 · View on GitHub

Motivation

Have you ever wondered how your GPS connects multiple cities with the least amount of road? How do telephone, elecrical, or computer infrastructures know to set up a network using the least cable? Everything from road or pipeline construction to cluster analysis of machine learning are real-world examples of a Minimum Spanning Tree. Understanding MST helps solve problems efficiently for this such as:

Prerequisites

Time Estimate

  • Reading Time: 30-45 minutes
  • Hands-on Activities: 1-2 hours
  • Total Learning Time: 2-3 hours

Terminology

  • Vertex (V): A node in the graph
  • Edge (E): A connection between two nodes with a weight
  • Cycle: A path that starts and ends at the same node without repeating edges
  • MST: A tree that connects all vertices with minimum total edge weight

Time and Space Complexity Reference

ComplexityDescriptionAlgorithm ContextGrowth CharacteristicsPractical Notes
O(E log V)Time complexity involving both edges (E) and logarithm of vertices (V)Prim's Algorithm with min-heap; Graph algorithms involving both vertices and edgesGrows logarithmically with vertices but scales linearly with edgesGreedy approach using min-heap; Slower than O(E log E) when E > V; Equivalent when E ≈ V
O(E log E)Time complexity where both linear and logarithmic factors depend on edgesKruskal's Algorithm; Graph algorithms with edge-based operationsSimilar to O(E log V) but grows faster when E > VGreedy approach using sorting + union-find; Common in algorithms that primarily operate on edges; Faster than O(E log V) when E > V
O(log N)Pure logarithmic complexity in terms of size NUnion-Find operations, Tree operations, General algorithmsPure logarithmic growth without additional scaling factorsGrows much slower than edge-based complexities; Gap widens significantly as E increases

Key Relationships: Both O(E log V) and O(E log E) scale linearly with E, but O(E log E) grows faster when E > V. Choice between algorithms depends on whether V or E is smaller in your specific graph structure.

What is a Minimum Spanning Tree?

A Minimum Spanning Tree (MST) of a weighted, connected, undirected graph is a subset of the edges that connects all vertices with the minimum total edge weight and no cycles.

Real-World Uses of MST

  • Designing road or pipeline networks.
  • Creating efficient communication networks.
  • Cluster analysis in Machine Learning.

Prim’s Algorithm

Strategy: Start with one vertex and grow the tree by adding the smallest edge connected to it.

Steps:

  1. Start with any node.
  2. Add the smallest edge that connects to a new node.
  3. Repeat until all nodes are included.

Data Structure Used: Min-Heap (Priority Queue)

Prim's Algorithm Animated Diagram

Prim-animation-wikipedia

Python Starter Code 
import heapq

def prim(graph, start):
    visited = set()
    min_heap = [(0, start)]
    total_weight = 0

    while min_heap:
        weight, node = heapq.heappop(min_heap)
        if node in visited:
            continue
        visited.add(node)
        total_weight += weight
        for neighbor, edge_weight in graph[node]:
            if neighbor not in visited:
                heapq.heappush(min_heap, (edge_weight, neighbor))

    return total_weight

Kruskal’s Algorithm

Strategy: Add the smallest edge without forming a cycle until all nodes are connected.

Steps:

  1. Sort all edges by weight.
  2. Initialize each node as its own tree.
  3. Add edges one by one — skip if they create a cycle.
  4. Stop when MST has (V-1) edges.

Data Structure Used: Disjoint Set (Union-Find)

Union Find Kruskal Animation

Union Find Kruskal Demo

Python Starter Code 
def find(parent, i):
    if parent[i] != i:
        parent[i] = find(parent, parent[i])
    return parent[i]

def union(parent, rank, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)
    if rank[root_x] < rank[root_y]:
        parent[root_x] = root_y
    elif rank[root_x] > rank[root_y]:
        parent[root_y] = root_x
    else:
        parent[root_y] = root_x
        rank[root_x] += 1

def kruskal(V, edges):
    parent = [i for i in range(V)]
    rank = [0] * V
    result = []
    edges.sort(key=lambda x: x[2])  # Sort by weight

    for u, v, weight in edges:
        if find(parent, u) != find(parent, v):
            union(parent, rank, u, v)
            result.append((u, v, weight))

    return result

⚠️ Note: When the graph is dense (many edges), Prim’s is usually faster. When the graph is sparse, both perform similarly.

Further Learning Resources