Minimum Spanning Tree
A Minimum Spanning Tree (MST) is a subset of edges that connects all vertices with minimum total weight and no cycles. Two popular algorithms: Prim's and Kruskal's.
Prim's Algorithm (starts from a node, grows tree)
Uses a priority queue to pick the smallest edge connecting the tree to outside. Time O((V+E) log V).
public int primMST() {
int[] minEdge = new int[V];
Arrays.fill(minEdge, Integer.MAX_VALUE);
minEdge[0] = 0;
boolean[] inMST = new boolean[V];
PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{0, 0});
int totalWeight = 0;
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int u = curr[0];
if (inMST[u]) continue;
inMST[u] = true;
totalWeight += curr[1];
for (Edge e : adjList[u]) {
if (!inMST[e.to] && e.weight < minEdge[e.to]) {
minEdge[e.to] = e.weight;
pq.offer(new int[]{e.to, e.weight});
}
}
}
return totalWeight;
}
Kruskal's Algorithm (uses union-find, picks smallest edges)
Sort edges, add if no cycle. Time O(E log E).
Two Minute Drill
- MST connects all vertices with minimum total weight.
- Prim's: starts from a node, grows tree with min edge (priority queue).
- Kruskal's: sorts edges, uses union-find to avoid cycles.
- Used in network design, clustering.
Need more clarification?
Drop us an email at career@quipoinfotech.com