Minimum Spanning Trees — Kruskal’s & Prim’s Algorithms Explained | Chapter 21 in Introduction to Algorithms

Chapter 21 of Introduction to Algorithms (CLRS) dives deep into one of the most elegant and widely used topics in graph theory: the minimum spanning tree (MST). MST algorithms are essential in network design, clustering, and optimization problems. This chapter introduces the MST problem, explains the greedy strategy behind its solutions, and breaks down two classic algorithms—Kruskal’s and Prim’s—used to efficiently construct MSTs.

📺 Watch the video above for a podcast-style walkthrough, or read below for a complete written summary and key definitions you need to understand this foundational algorithmic concept.

What Is a Minimum Spanning Tree?

A minimum spanning tree is a subset of a graph’s edges that connects all the vertices together without forming cycles and with the least possible total edge weight. The MST of a connected, undirected, weighted graph ensures that every vertex is included while minimizing cost—making it essential in areas like electrical wiring, computer networks, and transportation grids.

• Spanning Tree: Includes all vertices and exactly |V| – 1 edges.
• Applications: Used in network design, approximation algorithms, and caching.

The Greedy Strategy and Safe Edges

MST algorithms apply a greedy approach—choosing the smallest edge that safely connects components without forming a cycle. The concept of a safe edge is central to these strategies.

• Cut: Partition of vertices into two disjoint sets (S, V \ S).
• Light Edge: The smallest-weight edge crossing a cut.
• Theorem 21.1: A light edge across any cut that respects the partial MST is guaranteed to be safe.

Kruskal’s Algorithm

Kruskal’s algorithm builds the MST edge-by-edge by always choosing the next smallest weight edge that connects two different components. It’s efficient for sparse graphs and relies on a disjoint-set data structure to keep track of connected components.

• Sort all edges by weight.
• Use FIND-SET(u) and FIND-SET(v) to determine if edge (u, v) forms a cycle.
• If it doesn’t, add the edge and merge the components with UNION(u, v).
• Time Complexity: O(E log V), driven by edge sorting and disjoint-set operations.

Prim’s Algorithm

Prim’s algorithm grows the MST from a chosen root vertex by always adding the next lightest edge that connects the tree to a new vertex. It maintains a min-priority queue to efficiently find the next vertex to add.

• Each vertex v has a key (lightest edge weight to the MST) and a parent pointer π.
• Extract the vertex with the smallest key, then update neighbors via DECREASE-KEY.
• Time Complexity: O(E log V) with binary heap, O(E + V log V) with Fibonacci heap.

Advanced MST Topics

In the exercises and extensions, Chapter 21 covers additional MST-related problems and optimizations:

• Second-Best MST: The next-lowest-weight spanning tree.
• MST-REDUCE: Contracts edges to speed up Prim’s runtime to O(E log log V) in sparse graphs.
• Bottleneck Spanning Tree: Minimizes the largest edge in the spanning tree.
• Component Graphs: Used in Kruskal’s algorithm to represent connected components.

Glossary of Key Terms

• Minimum Spanning Tree (MST): Tree with minimum total edge weight connecting all vertices.
• Light Edge: Smallest weight edge across a cut.
• Safe Edge: Guaranteed to be in some MST without creating a cycle.
• Cut: A division of vertices into two disjoint subsets.
• Disjoint-Set Data Structure: Supports FIND-SET and UNION operations.
• Min-Priority Queue: Data structure that supports EXTRACT-MIN and DECREASE-KEY.
• Bottleneck Spanning Tree: A spanning tree minimizing the largest edge weight.
• Second-Best MST: An MST alternative with the next lowest total weight.

Conclusion

Minimum spanning tree algorithms are not only conceptually elegant but also immensely practical. By using a greedy strategy and safe-edge selection, Kruskal’s and Prim’s algorithms deliver efficient solutions to complex network problems. Mastery of these concepts is essential for anyone diving into graph theory, algorithm design, or competitive programming.

🎓 Want a step-by-step visual guide? Watch the full chapter summary here.

📘 For more insights from Introduction to Algorithms, don’t forget to explore additional chapters on the Last Minute Lecture YouTube channel.

If you found this breakdown helpful, be sure to subscribe to Last Minute Lecture for more chapter-by-chapter textbook summaries and academic study guides.