Minimum Spanning Tree (MST)
Definition
A Minimum Spanning Tree is a subset of edges in a connected, weighted graph that connects all vertices together without any cycles and with the minimum total edge weight.
Real-World Analogy
Laying Internet Cables: You need to connect 5 office buildings with fiber optic cable. Digging paths costs money. You want to connect all buildings so everyone has internet, but you want to dig the least amount of distance possible. You don’t need loops (redundant paths); you just need everything connected.
Two Main Algorithms
- Prim’s Algorithm:
- Start at one node.
- Grow the tree by always adding the cheapest edge that connects a node inside the tree to one outside.
- Similar to Dijkstra.
- Kruskal’s Algorithm:
- Sort all edges by weight (smallest to largest).
- Iterate through sorted edges. Add the edge to the tree unless it creates a cycle.
- Uses Disjoint Set Union (DSU) to check for cycles.
Code Example (Kruskal’s Logic)
Use Cases
PythonJavaCC++
# Disjoint Set Union (Union-Find)
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
self.parent[rootX] = rootY
# Kruskal's Algorithm
def kruskal(edges, num_vertices):
edges.sort() # Sort edges by weight
mst = []
dsu = DSU(num_vertices)
for weight, u, v in edges:
if dsu.find(u) != dsu.find(v):
dsu.union(u, v)
mst.append((u, v, weight))
return mst
edges = [
(10,0,1),
(6,0,2),
(5,0,3),
(15,1,3),
(4,2,3)
]
print("MST:", kruskal(edges, 4))
import java.util.*;
class DSU {
int[] parent;
DSU(int n) {
parent = new int[n];
for (int i = 0; i a[0]));
DSU dsu = new DSU(n);
List<int[]> mst = new ArrayList<>();
for (int[] e : edges) {
int w = e[0];
int u = e[1];
int v = e[2];
if (dsu.find(u) != dsu.find(v)) {
dsu.union(u, v);
mst.add(new int[]{u,v,w});
}
}
return mst;
}
public static void main(String[] args) {
int[][] edges = {
{10,0,1},
{6,0,2},
{5,0,3},
{15,1,3},
{4,2,3}
};
List<int[]> mst = kruskal(edges,4);
System.out.println("MST:");
for (int[] e : mst)
System.out.println(e[0] + " - " + e[1] + " : " + e[2]);
}
}
#include <stdio.h>
#include <stdlib.h>
struct Edge {
int weight, u, v;
};
int parent[100];
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
void unionSet(int x, int y) {
int rootX = find(x);
int rootY = find(y);
parent[rootX] = rootY;
}
int compare(const void* a, const void* b) {
struct Edge* e1 = (struct Edge*)a;
struct Edge* e2 = (struct Edge*)b;
return e1->weight - e2->weight;
}
void kruskal(struct Edge edges[], int E, int V) {
qsort(edges, E, sizeof(struct Edge), compare);
for (int i = 0; i < V; i++)
parent[i] = i;
printf("MST:\n");
for (int i = 0; i < E; i++) {
int u = edges[i].u;
int v = edges[i].v;
if (find(u) != find(v)) {
unionSet(u,v);
printf("%d - %d : %d\n", u, v, edges[i].weight);
}
}
}
int main() {
struct Edge edges[] = {
{10,0,1},
{6,0,2},
{5,0,3},
{15,1,3},
{4,2,3}
};
kruskal(edges,5,4);
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class DSU {
public:
vector<int> parent;
DSU(int n) {
parent.resize(n);
for (int i = 0; i < n; i++)
parent[i] = i;
}
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
parent[rootX] = rootY;
}
};
struct Edge {
int weight, u, v;
};
bool cmp(Edge a, Edge b) {
return a.weight < b.weight;
}
int main() {
vector<Edge> edges = {
{10,0,1},
{6,0,2},
{5,0,3},
{15,1,3},
{4,2,3}
};
sort(edges.begin(), edges.end(), cmp);
DSU dsu(4);
cout << "MST:\n";
for (auto e : edges) {
if (dsu.find(e.u) != dsu.find(e.v)) {
dsu.unite(e.u, e.v);
cout << e.u << " - "
<< e.v << " : "
<< e.weight << endl;
}
}
return 0;
}
- Network Design: Telecommunication cables, electrical grids, water pipelines.
- Cluster Analysis: Grouping similar items in Machine Learning.