Minimum Spanning Tree Calculator
Kruskal's Algorithm · Prim's Algorithm · Graph Visualization
Enter a weighted undirected graph as an edge list and compute the MST using both Kruskal's and Prim's algorithms. See step-by-step tables and a canvas visualization.
Quick Examples
MST Edge List
No results yet
Enter edges on the Calculator tab and click Compute MST.
Kruskal's Algorithm — Steps
Edges are processed in ascending weight order. Green rows = added to MST. Yellow rows = skipped (would form a cycle).
| Step | Edge | Weight | Action | Components |
|---|
No results yet
Enter edges on the Calculator tab and click Compute MST.
Prim's Algorithm — Steps
Starting from the selected node, the MST grows by always picking the minimum-weight edge to an unvisited vertex.
| Step | Node Added | Via Edge | Weight | MST so far |
|---|
No results yet
Enter edges on the Calculator tab and click Compute MST.
Graph Visualization
MST edge Non-MST edge
What Is a Spanning Tree?
A spanning tree of a connected undirected graph G = (V, E) is a subgraph that includes all vertices V and a subset of edges forming a tree — a connected, acyclic graph. For a graph with n vertices, every spanning tree has exactly n−1 edges. The concept is fundamental to network design, where you want every node reachable from every other node with no redundant connections.
What Is a Minimum Spanning Tree?
A minimum spanning tree (MST) is a spanning tree whose total edge weight is minimised over all possible spanning trees of the graph. Given a weighted undirected graph, the MST answers the question: "What is the cheapest way to connect all vertices?" For a graph with n vertices and m edges, the MST contains exactly n−1 edges and its total weight is the smallest achievable.
Two classical greedy algorithms solve this problem efficiently: Kruskal's algorithm and Prim's algorithm. Both are guaranteed to find an MST, and when all edge weights are distinct they both find the same unique tree.
Kruskal's Algorithm
Kruskal's algorithm processes edges globally, sorted by weight. It starts with each vertex in its own component and merges components by greedily adding the cheapest edge that does not create a cycle.
Steps
- Sort all edges by weight in ascending order.
- Initialize a Union-Find (disjoint set) structure with each vertex as its own set.
- For each edge (u, v, w) in sorted order: if u and v are in different components, add the edge to the MST and union the two components.
- Stop when n−1 edges have been added.
The Union-Find data structure with path compression and union by rank makes the cycle detection nearly O(1) per edge, giving Kruskal's algorithm an overall time complexity of O(E log E) — dominated by the sort.
Prim's Algorithm
Prim's algorithm grows the MST from a single starting vertex, always selecting the cheapest edge that connects the current MST to a vertex not yet in the tree.
Steps
- Start with any vertex; mark it visited.
- Add all edges from the current MST to a min-priority queue.
- Extract the minimum-weight edge (u, v) where v is unvisited; add it to the MST.
- Mark v visited and enqueue its edges. Repeat until n−1 edges are added.
With a binary heap, Prim's runs in O(E log V). With a Fibonacci heap it reaches O(E + V log V), which is superior for dense graphs.
Kruskal's vs Prim's — Comparison
| Property | Kruskal's | Prim's |
|---|---|---|
| Approach | Global edge sort | Vertex-by-vertex growth |
| Data Structure | Union-Find | Min-Heap / Priority Queue |
| Time Complexity | O(E log E) | O(E log V) |
| Best For | Sparse graphs | Dense graphs |
| Starting Point | None (all edges) | Chosen start vertex |
| Produces same MST? | Yes (for unique weights) | Yes (for unique weights) |
MST Uniqueness
An MST is unique if all edge weights are distinct. This follows from the cycle property: the maximum-weight edge in any cycle is never in any MST. When two edges share the same weight, multiple MSTs with equal total weight may exist. However, the total MST weight is always unique regardless of tie-breaking.
Disconnected Graphs — Spanning Forests
If the graph is disconnected, no spanning tree exists. Instead, each connected component has its own MST, and together they form a minimum spanning forest. For a graph with n vertices and k components, the spanning forest contains exactly n−k edges.
Real-World Applications
- Network Design: Designing telephone, power, or internet networks with minimum total cable length.
- Cable/Pipeline Laying: Finding the cheapest way to connect cities or infrastructure with physical links.
- Cluster Analysis: Single-linkage hierarchical clustering uses MSTs to group similar data points.
- TSP Approximation: The MST gives a 2-approximation for the metric Travelling Salesman Problem.
- Image Segmentation: Graph-based segmentation algorithms build MSTs over pixel similarity graphs.
- VLSI Circuit Design: Minimising wire length connecting circuit components on a chip.