Overview
A Minimum Spanning Tree (MST) is a subset of edges in a weighted undirected graph that connects all vertices with minimum total edge weight and no cycles. Kruskal’s algorithm efficiently finds the MST using a greedy approach with Disjoint Set Union.
Kruskal’s Algorithm
Kruskal’s algorithm builds the MST by:
- Sorting all edges by weight in ascending order
- Adding edges one by one if they don’t create a cycle
- Using DSU to efficiently detect cycles
Implementation
// graph_graph
// graph_undigraph
// graph_dsu
template <typename T>
vector<edge<T>> find_kruskal(const undigraph<T> &g, T &ans) {
vector<edge<T>> edges(g.edges);
sort(edges.begin(), edges.end(), [&g](const edge<T> &a, const edge<T> &b) {
return a.cost < b.cost;
});
ans = 0;
vector<edge<T>> mst;
DisjointSet dsu(g.n);
for(edge<T> e : edges) {
if(dsu.unite(e.from, e.to)) {
mst.push_back(e);
ans += e.cost;
}
}
return mst;
}
Usage Example
// Create an undirected graph
int n = 5;
undigraph<int> g(n);
// Add edges: (from, to, cost)
g.add(0, 1, 2);
g.add(0, 3, 6);
g.add(1, 2, 3);
g.add(1, 3, 8);
g.add(1, 4, 5);
g.add(2, 4, 7);
g.add(3, 4, 9);
// Find MST
int total_cost = 0;
vector<edge<int>> mst = find_kruskal(g, total_cost);
cout << "MST Cost: " << total_cost << "\n";
cout << "MST Edges:\n";
for(auto &e : mst) {
cout << e.from << " - " << e.to << " (cost: " << e.cost << ")\n";
}
MST Cost: 16
MST Edges:
0 - 1 (cost: 2)
1 - 2 (cost: 3)
1 - 4 (cost: 5)
0 - 3 (cost: 6)
Time Complexity: O(E log E) for sorting + O(E × α(V)) for DSU operations ≈ O(E log E)Space Complexity: O(E) for storing edgeswhere α is the inverse Ackermann function (effectively constant)
Disjoint Set Union (DSU)
Kruskal’s algorithm relies on DSU for efficient cycle detection. The DSU implementation is included:
class DisjointSet {
int n;
vector<int> parents;
vector<int> sizes;
public:
int comps; // Number of connected components
DisjointSet(int _n): n(_n), parents(n), sizes(n), comps(n) {
fill(sizes.begin(), sizes.end(), 1);
iota(parents.begin(), parents.end(), 0);
}
int find(int x) {
assert(0 <= x && x < n);
if (parents[x] != x)
parents[x] = find(parents[x]);
return parents[x];
}
bool unite(int left, int right) {
assert(0 <= left && left < n);
assert(0 <= right && right < n);
int x = find(left);
int y = find(right);
if(x == y)
return false;
if(sizes[x] < sizes[y])
swap(x, y);
sizes[x] += sizes[y];
parents[y] = x;
comps--;
return true;
};
bool united(int left, int right) {
assert(0 <= left && left < n);
assert(0 <= right && right < n);
return find(left) == find(right);
}
int size(int x) {
assert(0 <= x && x < n);
return sizes[find(x)];
}
int id(int x) {
assert(0 <= x && x < n);
return parents[find(x)];
}
};
using DSU = DisjointSet;
DSU Operations
- find(x): Returns the representative of the set containing x - O(α(n))
- unite(x, y): Merges the sets containing x and y - O(α(n))
- united(x, y): Checks if x and y are in the same set - O(α(n))
- size(x): Returns the size of the set containing x - O(α(n))
- comps: Tracks the number of connected components
Complete Example
#include <bits/stdc++.h>
using namespace std;
// Include graph structures and DSU
// ... (graph definitions)
// ... (DSU definition)
// ... (find_kruskal function)
int main() {
int n, m;
cin >> n >> m; // nodes and edges
undigraph<long long> g(n);
for(int i = 0; i < m; ++i) {
int u, v;
long long w;
cin >> u >> v >> w;
g.add(u, v, w);
}
long long mst_cost = 0;
vector<edge<long long>> mst = find_kruskal(g, mst_cost);
// Check if we have a spanning tree
if(mst.size() == n - 1) {
cout << "MST exists with cost: " << mst_cost << "\n";
} else {
cout << "Graph is not connected\n";
}
return 0;
}
A spanning tree of a graph with n vertices must have exactly n-1 edges. Check mst.size() == n - 1 to verify the graph is connected.
Properties of MST
- Uniqueness: If all edge weights are distinct, the MST is unique
- Edges: An MST of a graph with n vertices has exactly n-1 edges
- Connectivity: The MST connects all vertices with minimum total weight
- Cycle Property: For any cycle in the graph, the maximum weight edge is not in any MST
Common Applications
- Network Design: Connecting cities with minimum cable length
- Clustering: Grouping data points by removing expensive edges
- Approximation Algorithms: TSP approximations
- Image Segmentation: Computer vision applications
Kruskal’s algorithm only works on undirected graphs. For directed graphs, consider using the Chu-Liu/Edmonds’ algorithm for minimum spanning arborescence.