ayodhyya.comA Minimum Spanning Tree (MST) connects all vertices of a weighted undirected graph with minimal total edge weight. Two classic greedy algorithms—Prim's and Kruskal's—solve this problem efficiently.
The cut property ensures that the lightest edge crossing any cut belongs to some MST, providing the theoretical foundation for both algorithms.
Prim's Algorithm
Prim's algorithm grows the MST one vertex at a time by always adding the cheapest edge from the tree to a vertex outside it. It uses a priority queue to efficiently select the minimum weight frontier edge.
The time complexity is O((V+E) log V) with a binary heap, and it works best on dense graphs where adjacency lists are available.
vector>> primMST(vector>>& graph) {
int V = graph.size();
vector key(V, INT_MAX), parent(V, -1);
vector inMST(V, false);
priority_queue, vector>, greater<>> pq;
pq.push({0, 0}); key[0] = 0;
while (!pq.empty()) {
int u = pq.top().second; pq.pop();
inMST[u] = true;
for (auto [v, w] : graph[u])
if (!inMST[v] && w < key[v])
key[v] = w, parent[v] = u, pq.push({w, v});
}
vector>> mst(V);
for (int i = 1; i < V; i++)
mst[parent[i]].push_back({i, key[i]});
return mst;
} Kruskal's Algorithm
Kruskal's algorithm sorts all edges by weight and adds them greedily if they connect different components. A Union-Find data structure tracks component membership efficiently.
With O(E log E) sorting time, Kruskal is ideal for sparse graphs and naturally produces a forest of MSTs for disconnected graphs (MSF).
struct DSU {
vector parent, rank;
DSU(int n) : parent(n), rank(n, 0) { iota(parent.begin(), parent.end(), 0); }
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
bool unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return false;
if (rank[rx] < rank[ry]) parent[rx] = ry;
else if (rank[rx] > rank[ry]) parent[ry] = rx;
else parent[ry] = rx, rank[rx]++;
return true;
}
};
int kruskal(int V, vector>& edges) {
sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a[2] < b[2]; });
DSU dsu(V); int cost = 0;
for (auto& e : edges)
if (dsu.unite(e[0], e[1])) cost += e[2];
return cost;
} Frequently Asked Questions
What is the cut property in MST?
The cut property states that for any cut partitioning vertices into two sets, the minimum weight edge crossing the cut belongs to some MST. This justifies both Prim's and Kruskal's greedy edge selection.
Which MST algorithm is faster in practice?
Prim's with a Fibonacci heap achieves O(E + V log V) and excels on dense graphs. Kruskal's O(E log E) works better on sparse graphs and is simpler to implement.
Originally published on Ayodhyya. Last updated June 1, 2026.