Minimum Spanning Trees (MST)
A Minimum Spanning Tree (MST) of a connected, weighted, and undirected graph is a subset of the edges that connects all the vertices together, without any cycles, and with the minimum possible total edge weight.
1. Core Principles
- Spanning: It must contain a path between every pair of vertices.
- Tree: It must be acyclic (containing exactly $V - 1$ edges for a graph with $V$ vertices).
- Minimum: The sum of the edge weights must be the lowest possible among all spanning trees.
2. Primary Algorithms
I. Kruskal’s Algorithm (Greedy)
- Sort all edges in the graph by weight in non-decreasing order.
- Iterate through sorted edges. For each edge, add it to the MST only if it doesn't form a cycle.
- Use Disjoint Set Union (DSU) for efficient cycle detection.
- Complexity: O(E log E) or O(E log V).
- Best for: Sparse graphs.
II. Prim’s Algorithm (Greedy)
- Start with an arbitrary vertex and mark it as visited.
- In each step, find the minimum weight edge that connects a visited vertex to an unvisited vertex.
- Add the edge and the new vertex to the MST.
- Complexity: O(E log V) with a Priority Queue.
- Best for: Dense graphs.
3. Complexity Summary
| Algorithm | Complexity | Data Structure |
|---|---|---|
| Kruskal's | O(E log E) | DSU + Sorting |
| Prim's (Standard) | O(V²) | Adjacency Matrix |
| Prim's (Optimized) | O(E log V) | Adjacency List + Min-Heap |
4. Practical Applications
- Network Design: Minimizing the amount of cable needed to connect all houses in a neighborhood to a telecommunications network.
- Cluster Analysis: Used in Kruskal-based clustering to find "Nearest Neighbors."
- Circuit Design: Minimizing the electrical wire length on a motherboard.
Interview Pro-Tips: Prim's vs. Kruskal's
If an interviewer asks which one to use:
- Think Density: For Sparse graphs (few edges), Kruskal's is usually easier to implement and highly efficient.
- Think Connectivity: For Dense graphs (many edges), Prim's with a Min-Heap or an Adjacency Matrix often performs better.
- Unique MST: If all edge weights are unique, the graph is guaranteed to have exactly one unique Minimum Spanning Tree.
Technical Summary
V-1 Edges: The requirement for a spanning tree.DSU: The engine for Kruskal's algorithm.Greedy: Both algorithms make locally optimal choices to find the global minimum.Cycles: The primary constraint that must be avoided during construction.