Minimum Spanning Tree (MST) is a fundamental concept in graph theory and algorithms. Given a connected, weighted graph, an MST is a spanning tree (a subset of the edges that keeps the graph connected without any cycles) that has the minimum possible total edge weight. In other words, the MST connects all vertices together with the smallest total cost. For example, if vertices represent cities and edge weights represent the cost of building roads between them, an MST would be the set of roads connecting all cities at the lowest total cost.
n
vertices,
any spanning tree connects all vertices with exactly n-1
edges.
A spanning tree contains no cycles; removing any edge from it will disconnect the graph.MSTs have many practical applications where a set of points needs to be connected with minimal cost:
Kruskal’s algorithm builds an MST by iteratively adding the next smallest edge that doesn’t form a cycle. It treats the graph as a forest (collection of trees) and merges the trees together with lightest edges until a single tree spans all vertices. The algorithm steps are:
n-1
edges (where n
is the number of vertices).This algorithm uses the Union-Find (Disjoint Set Union) data structure to efficiently check for cycles. Union-Find keeps track of which vertices are in the same connected component. When an edge connects two vertices that are already in the same component, it would form a cycle and is therefore skipped.
Below is pseudocode for Kruskal’s algorithm:
// Kruskal's MST Algorithm
Kruskal(G):
MST = ∅
for each vertex v in G:
MakeSet(v) // initialize disjoint sets
sort edges of G by weight (in increasing order)
for each edge (u,v) in sorted order:
if FindSet(u) ≠ FindSet(v): // if u and v are in different components
MST = Union(MST, {(u,v)}) // add edge to MST
Union(u, v) // merge the components
return MST
During the iteration, if an edge is rejected (because FindSet(u) == FindSet(v)
,
meaning there’s already a path between those vertices),
the algorithm moves on to the next edge. Kruskal’s algorithm has a time complexity of about O(E log E)
(dominated by sorting the edges), which is effectively O(E log V)
for a graph with V
vertices and E
edges.
Using Union-Find with path compression and union by rank, each union or find operation is almost constant time on average.
Prim’s algorithm builds the MST by starting from an arbitrary vertex and growing the tree one edge at a time. It maintains a set of vertices already in the MST and at each step adds the smallest weight edge that connects a vertex in the MST to a vertex outside the MST. The steps are:
n-1
edges).Prim’s algorithm can be efficiently implemented using a min-heap
(priority queue) to always pick the next smallest edge.
It typically runs in O(E log V)
time as well (or O(V2)
without a min-heap, if using a simple array to find the minimum edge each time).
The pseudocode for Prim’s algorithm is given below:
// Prim's MST Algorithm (assuming graph G with vertices V)
Prim(G):
MST = ∅
let U = { arbitrary start vertex }
while (U ≠ V):
// find the minimum weight edge (u, v) with u ∈ U and v ∉ U
find (u, v) with minimum weight such that u ∈ U and v ∉ U
MST = Union(MST, {(u, v)})
U = Union(U ∪ {v})
return MST
In practice, Prim’s algorithm starts from an initial vertex and uses a priority queue to track the cheapest edge leading out from the current tree.
Each time a new vertex v
is added to the MST, the edges from v
to its neighbors are examined to update the candidate edges.
Unselected edges that would form a cycle (connecting to a vertex already in U
) are ignored implicitly, because the algorithm always picks an edge connecting to a new vertex.
Prim’s and Kruskal’s algorithms will both yield an MST when applied correctly, but they build the tree in different ways
– Prim’s grows one connected component, whereas Kruskal’s can connect components in any order.
Algorithm | Approach | Data Structures | Time Complexity | When to Use |
---|---|---|---|---|
Kruskal’s | Greedy by edge weight (global minimum edges first) | Union-Find for cycle detection; sorting of edges | O(E log V) (due to sorting edges) | Good for sparse graphs; easy to implement if edges are readily available |
Prim’s | Greedy by growing a tree (local minimum edge from current tree) | Priority queue (min-heap) for selecting next edge; adjacency list | O(E log V) (with min-heap) or O(V2) without heap | Often chosen for dense graphs or when adjacency list is available for efficiency |
Below, you can interactively visualize how Kruskal’s and Prim’s algorithms construct an MST. Select an algorithm, then click "Start" to initialize. Use "Next Step" to advance the algorithm step by step. The graph’s vertices (A–F) are connected by weighted edges. As you step through, edges chosen for the MST will be highlighted in green, and you’ll see which edges are added or skipped at each step.
Select an algorithm and click Start to begin.
To reinforce the concepts, try the following programming exercises in C++. You may use the Graph.h class for your implementation.
Test your implementation on a small graph (you can use the example graph from the visualization above) to ensure it picks the correct edges.
Answer: here
g.vertices()
)std::priority_queue
to always pick the next smallest edge. You can store entries of the form (weight, vertex)
in the priority queue representing the best edge to each candidate vertex.Ensure your program outputs the total weight of the MST and the list of edges chosen.
Answer: here