MSTs

MSTs, or minimum spanning trees, are a concept in graph theory used to describe a spanning tree with the smallest possible total edge weight in a connected weighted graph. A spanning tree is a subset of edges that connects all vertices without creating cycles. If the graph is not connected, the analogue is a minimum spanning forest, consisting of a minimum spanning tree for each connected component and having the smallest possible total weight across the graph.

Two standard methods to construct MSTs are Kruskal's algorithm and Prim's algorithm. Kruskal's algorithm processes edges in nondecreasing weight order, adding an edge whenever it connects two previously disconnected components, typically implemented with a union-find data structure. Prim's algorithm starts from an arbitrary vertex and repeatedly adds the lightest edge that connects the growing tree to a new vertex, often using a priority queue. The typical running times are O(E log V) for Kruskal's algorithm (with sorting) and O(E log V) for Prim's algorithm using a binary heap; with advanced data structures, Prim's algorithm can achieve better theoretical performance in some cases.

Key properties of MSTs include the cycle property and the cut property. The cycle property states that in any cycle, the heaviest edge cannot belong to any MST. The cut property states that for any cut in the graph, the lightest crossing edge belongs to all MSTs. If all edge weights are distinct, the MST is unique; otherwise, multiple MSTs with the same total weight may exist.

MSTs have applications in network design, such as laying out efficient communication or transportation networks, and in data analysis tasks like hierarchical clustering. They also serve as a foundational concept in various optimization and approximation algorithms.