Minimum Spanning Tree
Last updated
Last updated
A minimum-spanning-tree is a tree (without cycles) connecting all the vertices and with the smallest cost.
Prim's (O(ElogV)) is more performant on dense graph. Kruskal's (O(ElogE)) is more performant on sparse graph.
| Aspect | Prim's Algorithm | Kruskal's Algorithm |
|---|---|---|
1584. Min Cost to Connect All Points (Medium) Dense Graph. Prim is better.
Algorithm Type
Greedy
Greedy
Edge Selection
Chooses the minimum-weight edge connected to the current MST.
Sorts all edges by weight and adds them to the MST if they don't form a cycle.
Data Structures Used
Priority queue or min-heap (to efficiently select the minimum-weight edge).
Disjoint-set data structure (to check for cycles).
Complexity
O(V^2) using an adjacency matrix, O(E + V log V) using a binary heap for dense graphs.
O(E log E) to sort the edges, O(E log V) to process all edges and find MST using disjoint-set.
Suitability
More efficient for dense graphs (E is close to V^2).
Suitable for sparse graphs (E is much less than V^2).
Applications
Network design, clustering, road planning, maze generation, etc.
Network design, cluster analysis, image segmentation, etc.
Cycle Handling
Doesn't directly deal with cycles; relies on the connectedness of the graph.
Detects and avoids cycles explicitly.
Output
Yields a single MST rooted at a selected vertex.
Yields a forest of MSTs initially; they combine into a single MST as more edges are added.