Minimum Spanning Tree (MST)

overview

Summary

A minimum spanning tree (MST) connects all vertices in a weighted, undirected, connected graph with the minimum total edge weight and no cycles. It is a foundational concept for network design, clustering, and other optimization problems. Classic algorithms include Kruskal and Prim, both relying on greedy choices justified by cut and cycle properties. Efficient MST solutions hinge on the right data structures, like union find and priority queues.