Minimum Spanning Tree

Analogy categoryAnalogies

Introduction

A Minimum Spanning Tree (MST) of a connected, undirected, weighted graph is a subset of edges that connects all vertices together, contains no cycles, and has the minimum possible total edge weight. MSTs are used in network design (minimizing cable length to connect all cities), clustering, and approximation algorithms. Two classic greedy algorithms solve this problem optimally: Kruskal's algorithm, which sorts edges globally, and Prim's algorithm, which grows the tree from a single vertex.

🏏

Cricket analogy: An MST is like laying the cheapest set of practice-ground connections linking every regional academy with no wasted duplicate routes and no redundant loops; Kruskal's approach ranks every possible connection nationally by cost, while Prim's grows the network out from a single home academy.

Representation/Syntax

python

class UnionFind:
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}

    def find(self, v):
        if self.parent[v] != v:
            self.parent[v] = self.find(self.parent[v])  # path compression
        return self.parent[v]

    def union(self, u, v):
        root_u, root_v = self.find(u), self.find(v)
        if root_u == root_v:
            return False  # already connected -> would form a cycle
        if self.rank[root_u] < self.rank[root_v]:
            root_u, root_v = root_v, root_u
        self.parent[root_v] = root_u
        if self.rank[root_u] == self.rank[root_v]:
            self.rank[root_u] += 1
        return True

Explanation

Kruskal's algorithm sorts all edges by weight in ascending order, then greedily adds each edge to the MST as long as it does not create a cycle. Cycle detection is done efficiently with a Union-Find (Disjoint Set Union) structure: two vertices are in the same set if they are already connected in the growing MST, so an edge is only added if its endpoints belong to different sets, after which the sets are merged. The algorithm stops once V-1 edges have been added, since a spanning tree on V vertices always has exactly V-1 edges.

🏏

Cricket analogy: Kruskal's approach ranks every possible ground-to-ground connection by cost from cheapest to priciest, adding each one only if it doesn't create a redundant loop back to an already-linked region, checked instantly via a union-find registry of which academies are already grouped, stopping once V-1 links join all V academies.

Example

python

def kruskal_mst(vertices, edges):
    # edges: list of (weight, u, v)
    uf = UnionFind(vertices)
    mst = []
    total_weight = 0

    for weight, u, v in sorted(edges):
        if uf.union(u, v):
            mst.append((u, v, weight))
            total_weight += weight
        if len(mst) == len(vertices) - 1:
            break

    return mst, total_weight

vertices = ['A', 'B', 'C', 'D', 'E']
edges = [
    (2, 'A', 'B'), (3, 'A', 'C'), (4, 'B', 'C'),
    (1, 'B', 'D'), (5, 'C', 'D'), (6, 'D', 'E')
]

mst, total = kruskal_mst(vertices, edges)
print('MST edges:', mst)
print('Total weight:', total)

Complexity

Sorting E edges costs O(E log E), and processing each edge with Union-Find (using path compression and union by rank) costs nearly O(1) amortized (technically O(alpha(V)), the inverse Ackermann function). Overall Kruskal's algorithm runs in O(E log E) time, which is equivalent to O(E log V) since E is at most V^2. Prim's algorithm with a binary heap achieves O(E log V) as well, and is often preferred for dense graphs when implemented with an adjacency matrix in O(V^2).

🏏

Cricket analogy: Ranking all E possible ground connections costs O(E log E), and checking each one against the union-find registry costs nearly O(1) thanks to path compression, so Kruskal's overall O(E log E) equals O(E log V); Prim's approach with a binary heap achieves the same O(E log V), and is favored for dense fixture networks using an adjacency matrix at O(V^2).

Key Takeaways

An MST connects all V vertices with exactly V-1 edges at minimum total weight, with no cycles.
Kruskal's algorithm sorts edges and greedily adds them if they don't form a cycle, using Union-Find.
Union-Find with path compression and union by rank makes cycle checks nearly O(1) amortized.
Kruskal's runs in O(E log E) time overall, dominated by the initial edge sort.
Prim's algorithm is an alternative that grows the MST from a starting vertex, useful for dense graphs.

Practice what you learned

1. How many edges does a Minimum Spanning Tree contain for a graph with V vertices?

2. What data structure does Kruskal's algorithm use to efficiently detect cycles?

3. What is the overall time complexity of Kruskal's algorithm?

4. In Kruskal's algorithm, what happens when an edge's two endpoints already belong to the same Union-Find set?

5. Which technique used in Union-Find keeps the find() operation nearly constant time?

Was this page helpful?

Shortest Path Algorithms

Topological Sort

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#MinimumSpanningTree#Minimum#Spanning#Tree#Representation#StudyNotes#SkillVeris