Minimum Spanning Trees

Getting Started with Competitive Programming

(an NPTEL course)

Week 7. Minimum Spanning Trees

In this week, we study two popular algorithms for finding Minimum Spanning Trees (namely Prim's algorithm and Kruskal's algorithm), and also look at one variant in the context of an application.

Class Plan & Materials

A. Prerequisites
1. MST Foundations: Prim and Kruskal's Algorithms
2. Cherries Mesh
3. Hierarchy
4. Island Hopping
Z. Extras