Posted on Sep 1

📘 Blog 6: Minimum Spanning Tree (MST) 🌉

🔹 What is MST?

A Spanning Tree of a graph connects all vertices with the minimum number of edges (N-1 for N nodes), with no cycles.
A Minimum Spanning Tree (MST) is the spanning tree where the sum of edge weights is minimized.

✅ Graph must be:

Connected
Undirected
Weighted

🔹 Why is MST Important?

Network Design: Build road, cable, or data network with minimum cost.
Clustering Algorithms (ML): Partitioning data.
Approximation Algorithms: TSP, Steiner Tree.

🔹 MST Algorithms

We mainly use Kruskal’s and Prim’s.

1️⃣ Kruskal’s Algorithm (Union-Find / Greedy Approach)

Steps:

Sort all edges by weight.
Pick the smallest edge that doesn’t form a cycle.
Use Union-Find (Disjoint Set Union - DSU) to check cycle.
Repeat until you connect all vertices (N-1 edges).

Complexity:

Sorting edges: O(E log E)
Union-Find operations: ~O(E α(N)) (α(N) is inverse Ackermann, nearly constant).

👉 Best when graph is sparse (E ~ V).

Java Code (Kruskal’s MST):

import java.util.*; class KruskalMST { static class Edge { int u, v, weight; Edge(int u, int v, int weight) { this.u = u; this.v = v; this.weight = weight; } } static class DSU { int[] parent, rank; DSU(int n) { parent = new int[n]; rank = new int[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]; } boolean union(int x, int y) { int px = find(x), py = find(y); if (px == py) return false; if (rank[px] < rank[py]) parent[px] = py; else if (rank[px] > rank[py]) parent[py] = px; else { parent[py] = px; rank[px]++; } return true; } } public static int kruskalMST(int n, List<Edge> edges) { Collections.sort(edges, Comparator.comparingInt(e -> e.weight)); DSU dsu = new DSU(n); int mstCost = 0, count = 0; for (Edge edge : edges) { if (dsu.union(edge.u, edge.v)) { mstCost += edge.weight; count++; if (count == n - 1) break; } } return mstCost; } public static void main(String[] args) { List<Edge> edges = Arrays.asList( new Edge(0, 1, 10), new Edge(0, 2, 6), new Edge(0, 3, 5), new Edge(1, 3, 15), new Edge(2, 3, 4) ); System.out.println("MST Cost = " + kruskalMST(4, edges)); } }

✅ Output: MST Cost = 19

2️⃣ Prim’s Algorithm (Priority Queue / Greedy Approach)

Steps:

Start from any node.
Use a Min Heap to always pick the smallest edge connecting MST to a new node.
Expand MST until all nodes are covered.

Complexity:

With Min Heap (priority queue): O(E log V).

👉 Best when graph is dense (E ~ V²).

Java Code (Prim’s MST):

import java.util.*; class PrimsMST { static class Pair { int node, weight; Pair(int node, int weight) { this.node = node; this.weight = weight; } } public static int primMST(int n, List<List<Pair>> graph) { boolean[] visited = new boolean[n]; PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p.weight)); pq.offer(new Pair(0, 0)); // Start from node 0 int mstCost = 0; while (!pq.isEmpty()) { Pair cur = pq.poll(); if (visited[cur.node]) continue; visited[cur.node] = true; mstCost += cur.weight; for (Pair nei : graph.get(cur.node)) { if (!visited[nei.node]) pq.offer(nei); } } return mstCost; } public static void main(String[] args) { int n = 4; List<List<Pair>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) graph.add(new ArrayList<>()); graph.get(0).add(new Pair(1, 10)); graph.get(0).add(new Pair(2, 6)); graph.get(0).add(new Pair(3, 5)); graph.get(1).add(new Pair(3, 15)); graph.get(2).add(new Pair(3, 4)); System.out.println("MST Cost = " + primMST(n, graph)); } }