[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":87,"_73":88,"_35":89},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",40,"title","Minimum Spanning Trees","slug","algorithms-part-13-minimum-spanning-tree","excerpt","Build Union-Find with path compression and union by rank. Apply Kruskal's and Prim's algorithms to network design and clustering problems.","# Algorithms Compendium Part 13: Minimum Spanning Tree\n\nA spanning tree connects all vertices with exactly V-1 edges and no cycles. A Minimum Spanning Tree (MST) does this with minimum total edge weight. MST algorithms solve practical problems: network design, clustering, approximation algorithms, and more. This article covers Union-Find (the key data structure), Kruskal's greedy edge selection, Prim's greedy vertex growth, and their applications.\n\n## 📋 At a Glance\n\n| Algorithm | Time | Space | Best For |\n|-----------|------|-------|----------|\n| Kruskal | O(E log E) | O(V) | Sparse graphs, edge list input |\n| Prim (binary heap) | O(E log V) | O(V) | Dense graphs, adjacency list |\n| Prim (Fibonacci heap) | O(E + V log V) | O(V) | Very dense graphs |\n| Borůvka | O(E log V) | O(V) | Parallel implementation |\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Implement Union-Find** with path compression and union by rank\n- **Apply Kruskal's algorithm** for edge-based MST construction\n- **Use Prim's algorithm** for vertex-based MST growth\n- **Understand MST properties** and their proofs\n- **Solve practical problems** using MST (clustering, network design)\n- **Choose the right algorithm** based on graph characteristics\n\n---\n\n## 🔥 Production Story: The Network Infrastructure Optimization\n\nA telecom company needed to connect 50 data centers with fiber optic cables. Running cables between all pairs would cost billions. They needed the minimum-cost network that still connected everything.\n\n```java\n// ❌ Initial approach: Connect everything (not economical)\npublic class NetworkPlanner {\n public List planNetwork(List centers) {\n List connections = new ArrayList<>();\n\n // Connect all pairs - way too expensive!\n for (int i = 0; i < centers.size(); i++) {\n for (int j = i + 1; j < centers.size(); j++) {\n connections.add(new Connection(\n centers.get(i),\n centers.get(j),\n calculateCost(centers.get(i), centers.get(j))\n ));\n }\n }\n return connections; // 1225 connections for 50 centers!\n }\n}\n```\n\n**The problem:** Full mesh is O(V²) connections. With 50 centers, that's 1,225 connections at average $2M each = $2.45B.\n\n**The solution:**\n\n```java\n// ✅ MST: Minimum connections to reach all centers\npublic class OptimizedNetworkPlanner {\n public List planNetwork(List centers) {\n // Calculate all possible connections\n List edges = new ArrayList<>();\n for (int i = 0; i < centers.size(); i++) {\n for (int j = i + 1; j < centers.size(); j++) {\n edges.add(new Edge(i, j,\n calculateCost(centers.get(i), centers.get(j))));\n }\n }\n\n // Kruskal's algorithm for MST\n edges.sort(Comparator.comparingLong(Edge::cost));\n UnionFind uf = new UnionFind(centers.size());\n List mst = new ArrayList<>();\n\n for (Edge e : edges) {\n if (uf.find(e.from) != uf.find(e.to)) {\n uf.union(e.from, e.to);\n mst.add(new Connection(\n centers.get(e.from),\n centers.get(e.to),\n e.cost\n ));\n\n if (mst.size() == centers.size() - 1) break;\n }\n }\n\n return mst; // Only 49 connections!\n }\n}\n// Result: 49 connections, total cost $89M (vs $2.45B for full mesh)\n// Savings: 96.4%!\n```\n\n**Additional consideration - redundancy:**\n\n```java\n// ✅ k-MST variant for fault tolerance\npublic List planRedundantNetwork(List centers, int k) {\n // Start with MST\n List network = planNetwork(centers);\n\n // Add k more edges (cheapest remaining) for redundancy\n Set inNetwork = new HashSet<>();\n for (Connection c : network) {\n inNetwork.add(edgeKey(c));\n }\n\n List remaining = allEdges.stream()\n .filter(e -> !inNetwork.contains(edgeKey(e)))\n .sorted(Comparator.comparingLong(Edge::cost))\n .limit(k)\n .collect(Collectors.toList());\n\n // Add redundant connections\n for (Edge e : remaining) {\n network.add(new Connection(centers.get(e.from), centers.get(e.to), e.cost));\n }\n\n return network;\n}\n```\n\n**The lesson:** MST provides the minimum-cost connected network. Real applications often add redundancy on top of MST.\n\n---\n\n## 🧠 Mental Model: MST Properties\n\n```text\nMST FUNDAMENTAL PROPERTIES\n━━━━━━━━━━━━━━━━━━━━━━━━━\n\nProperty 1: Cut Property\n─────────────────────────\nFor any cut (partition of vertices into two sets),\nthe minimum-weight edge crossing the cut is in some MST.\n\n Set A Set B\n ┌───────┐ ┌───────┐\n │ ● ● │ │ ● ● │\n │ ● │──5───│ ● │ ← 5 is min crossing edge\n │ ● ● │──7───│ │ ← 7 is not min\n │ │──8───│ ● │ ← 8 is not min\n └───────┘ └───────┘\n\nEdge with weight 5 must be in MST!\n\n\nProperty 2: Cycle Property\n──────────────────────────\nFor any cycle, the maximum-weight edge is NOT in any MST.\n\n ●────5────●\n / \\\n 8 3\n / \\\n ●───────7────────●\n\nMax edge in cycle (8) is not in MST.\nMST uses edges: 5, 3, 7\n\n\nProperty 3: Uniqueness\n──────────────────────\nIf all edge weights are distinct, MST is unique.\nIf some weights are equal, there may be multiple valid MSTs.\n```\n\n---\n\n## 🔬 Deep Dive: Union-Find (Disjoint Set Union)\n\n### Basic Implementation\n\n```java\npublic class UnionFind {\n private final int[] parent;\n private final int[] rank;\n private int components;\n\n public UnionFind(int n) {\n parent = new int[n];\n rank = new int[n];\n components = n;\n\n for (int i = 0; i < n; i++) {\n parent[i] = i; // Each element is its own parent\n rank[i] = 0;\n }\n }\n\n /**\n * Find root of element x with path compression.\n * Time: O(α(n)) amortized ≈ O(1)\n */\n public int find(int x) {\n if (parent[x] != x) {\n parent[x] = find(parent[x]); // Path compression\n }\n return parent[x];\n }\n\n /**\n * Union two sets by rank.\n * Time: O(α(n)) amortized ≈ O(1)\n *\n * @return true if union happened (were in different sets)\n */\n public boolean union(int x, int y) {\n int rootX = find(x);\n int rootY = find(y);\n\n if (rootX == rootY) {\n return false; // Already in same set\n }\n\n // Union by rank: attach smaller tree under larger\n if (rank[rootX] < rank[rootY]) {\n parent[rootX] = rootY;\n } else if (rank[rootX] > rank[rootY]) {\n parent[rootY] = rootX;\n } else {\n parent[rootY] = rootX;\n rank[rootX]++;\n }\n\n components--;\n return true;\n }\n\n /**\n * Check if two elements are in the same set.\n */\n public boolean connected(int x, int y) {\n return find(x) == find(y);\n }\n\n /**\n * Get number of disjoint sets.\n */\n public int getComponents() {\n return components;\n }\n}\n```\n\n### Union-Find Visualization\n\n```text\nUNION-FIND OPERATIONS\n━━━━━━━━━━━━━━━━━━━━━\n\nInitial state (n=6):\n 0 1 2 3 4 5\n │ │ │ │ │ │\n 0 1 2 3 4 5\n\nAfter union(0, 1):\n 0 2 3 4 5\n │ │ │ │ │\n 1 2 3 4 5\n (1 points to 0)\n\nAfter union(2, 3):\n 0 2 4 5\n │ │ │ │\n 1 3 4 5\n\nAfter union(0, 2):\n 0 4 5\n /│ │ │\n 1 2 4 5\n │\n 3\n\nAfter find(3) with path compression:\n 0 4 5\n / | \\ │ │\n 1 2 3 4 5\n (3 now directly points to 0)\n```\n\n### Union-Find with Size (Alternative to Rank)\n\n```java\npublic class UnionFindBySize {\n private final int[] parent;\n private final int[] size;\n\n public UnionFindBySize(int n) {\n parent = new int[n];\n size = new int[n];\n for (int i = 0; i < n; i++) {\n parent[i] = i;\n size[i] = 1;\n }\n }\n\n public int find(int x) {\n if (parent[x] != x) {\n parent[x] = find(parent[x]);\n }\n return parent[x];\n }\n\n public boolean union(int x, int y) {\n int rootX = find(x);\n int rootY = find(y);\n\n if (rootX == rootY) return false;\n\n // Union by size: attach smaller tree under larger\n if (size[rootX] < size[rootY]) {\n parent[rootX] = rootY;\n size[rootY] += size[rootX];\n } else {\n parent[rootY] = rootX;\n size[rootX] += size[rootY];\n }\n return true;\n }\n\n public int getSize(int x) {\n return size[find(x)];\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Kruskal's Algorithm\n\n### The Algorithm\n\n```java\npublic class Kruskal {\n /**\n * Kruskal's MST algorithm.\n *\n * Time: O(E log E) for sorting edges\n * Space: O(V) for Union-Find\n */\n public static List mst(int vertices, List edges) {\n // Sort edges by weight\n List sortedEdges = new ArrayList<>(edges);\n sortedEdges.sort(Comparator.comparingInt(e -> e.weight));\n\n UnionFind uf = new UnionFind(vertices);\n List mst = new ArrayList<>();\n\n for (Edge e : sortedEdges) {\n // If edge connects two different components, add to MST\n if (uf.union(e.from, e.to)) {\n mst.add(e);\n\n // MST has exactly V-1 edges\n if (mst.size() == vertices - 1) {\n break;\n }\n }\n }\n\n return mst;\n }\n\n /**\n * Calculate total MST weight.\n */\n public static int mstWeight(int vertices, List edges) {\n return mst(vertices, edges).stream()\n .mapToInt(e -> e.weight)\n .sum();\n }\n\n public record Edge(int from, int to, int weight) {}\n}\n```\n\n### Kruskal's Visualization\n\n```text\nKRUSKAL'S ALGORITHM EXAMPLE\n━━━━━━━━━━━━━━━━━━━━━━━━━━━\n\nGraph:\n 0───4───1\n │\\ /│\n │ 8 2 │\n │ \\ / │\n 3 ╳ 6\n │ / \\ │\n │ 7 1 │\n │/ \\│\n 2───5───3\n\nEdges sorted: (1,3,1), (0,1,2), (0,2,3), (1,3,4), (0,3,5), (2,3,5), ...\n\nStep 1: Add (1,3,1) - connects 1 and 3\nStep 2: Add (0,1,2) - connects 0 to {1,3}\nStep 3: Add (0,2,3) - connects 2 to {0,1,3}\nStep 4: Skip (1,3,4) - would create cycle (1 and 3 already connected)\nStep 5: Done! V-1 = 3 edges\n\nMST edges: (1,3), (0,1), (0,2)\nTotal weight: 1 + 2 + 3 = 6\n```\n\n---\n\n## 🔬 Deep Dive: Prim's Algorithm\n\n### Priority Queue Implementation\n\n```java\npublic class Prim {\n /**\n * Prim's MST algorithm using priority queue.\n *\n * Time: O(E log V) with binary heap\n * Space: O(V)\n */\n public static List mst(WeightedGraph graph) {\n int n = graph.getVertices();\n boolean[] inMST = new boolean[n];\n int[] key = new int[n]; // Minimum weight to connect vertex\n int[] parent = new int[n]; // Parent in MST\n\n Arrays.fill(key, Integer.MAX_VALUE);\n Arrays.fill(parent, -1);\n\n // Start from vertex 0\n key[0] = 0;\n\n // PQ: [vertex, key]\n PriorityQueue pq = new PriorityQueue<>(\n Comparator.comparingInt(a -> a[1])\n );\n pq.offer(new int[]{0, 0});\n\n List mst = new ArrayList<>();\n\n while (!pq.isEmpty()) {\n int[] curr = pq.poll();\n int u = curr[0];\n\n if (inMST[u]) continue;\n inMST[u] = true;\n\n // Add edge to MST (except for starting vertex)\n if (parent[u] != -1) {\n mst.add(new Edge(parent[u], u, key[u]));\n }\n\n // Update keys of adjacent vertices\n for (WeightedGraph.Edge e : graph.neighbors(u)) {\n int v = e.to();\n int weight = e.weight();\n\n if (!inMST[v] && weight < key[v]) {\n key[v] = weight;\n parent[v] = u;\n pq.offer(new int[]{v, weight});\n }\n }\n }\n\n return mst;\n }\n\n public record Edge(int from, int to, int weight) {}\n}\n```\n\n### Prim's with Adjacency Matrix (Dense Graphs)\n\n```java\npublic class PrimDense {\n /**\n * Prim's for dense graphs using adjacency matrix.\n * Better when E ≈ V² because avoids PQ overhead.\n *\n * Time: O(V²)\n * Space: O(V)\n */\n public static int mstWeight(int[][] graph) {\n int n = graph.length;\n boolean[] inMST = new boolean[n];\n int[] key = new int[n];\n\n Arrays.fill(key, Integer.MAX_VALUE);\n key[0] = 0;\n\n int totalWeight = 0;\n\n for (int count = 0; count < n; count++) {\n // Find minimum key vertex not in MST\n int u = -1;\n for (int v = 0; v < n; v++) {\n if (!inMST[v] && (u == -1 || key[v] < key[u])) {\n u = v;\n }\n }\n\n inMST[u] = true;\n totalWeight += key[u];\n\n // Update keys of adjacent vertices\n for (int v = 0; v < n; v++) {\n if (graph[u][v] != 0 && !inMST[v] && graph[u][v] < key[v]) {\n key[v] = graph[u][v];\n }\n }\n }\n\n return totalWeight;\n }\n}\n```\n\n### Prim's Visualization\n\n```text\nPRIM'S ALGORITHM EXAMPLE\n━━━━━━━━━━━━━━━━━━━━━━━━\n\nSame graph, starting from vertex 0:\n\nInitial:\n key = [0, ∞, ∞, ∞]\n MST = {}\n\nStep 1: Pick vertex 0 (key=0)\n Update neighbors: key[1]=2, key[2]=3\n MST = {}\n\nStep 2: Pick vertex 1 (key=2)\n Update neighbors: key[3]=1\n MST = {(0,1)}\n\nStep 3: Pick vertex 3 (key=1)\n MST = {(0,1), (1,3)}\n\nStep 4: Pick vertex 2 (key=3)\n MST = {(0,1), (1,3), (0,2)}\n\nSame result as Kruskal's!\n```\n\n---\n\n## 🔬 Deep Dive: Borůvka's Algorithm\n\n### Parallel-Friendly MST\n\n```java\npublic class Boruvka {\n /**\n * Borůvka's MST algorithm.\n * Naturally parallelizable - each component finds its minimum edge independently.\n *\n * Time: O(E log V)\n * Space: O(V)\n */\n public static List mst(int vertices, List edges) {\n UnionFind uf = new UnionFind(vertices);\n List mst = new ArrayList<>();\n\n int components = vertices;\n\n while (components > 1) {\n // For each component, find minimum outgoing edge\n int[] cheapest = new int[vertices];\n Arrays.fill(cheapest, -1);\n\n for (int i = 0; i < edges.size(); i++) {\n Edge e = edges.get(i);\n int root1 = uf.find(e.from);\n int root2 = uf.find(e.to);\n\n if (root1 == root2) continue; // Same component\n\n // Update cheapest edge for both components\n if (cheapest[root1] == -1 || edges.get(cheapest[root1]).weight > e.weight) {\n cheapest[root1] = i;\n }\n if (cheapest[root2] == -1 || edges.get(cheapest[root2]).weight > e.weight) {\n cheapest[root2] = i;\n }\n }\n\n // Add cheapest edges to MST\n for (int i = 0; i < vertices; i++) {\n if (cheapest[i] != -1) {\n Edge e = edges.get(cheapest[i]);\n if (uf.union(e.from, e.to)) {\n mst.add(e);\n components--;\n }\n }\n }\n }\n\n return mst;\n }\n\n public record Edge(int from, int to, int weight) {}\n}\n```\n\n### Algorithm Comparison\n\n| Aspect | Kruskal | Prim | Borůvka |\n|--------|---------|------|---------|\n| Strategy | Sort edges, add if no cycle | Grow tree from vertex | Each component finds min edge |\n| Data structure | Union-Find | Priority Queue | Union-Find |\n| Better for | Sparse graphs | Dense graphs | Parallel systems |\n| Edge format | Edge list | Adjacency list | Edge list |\n\n---\n\n## 🔬 Deep Dive: MST Applications\n\n### Clustering (Single-Linkage)\n\n```java\npublic class MSTClustering {\n /**\n * Cluster data points using MST.\n * Remove k-1 longest edges to get k clusters.\n */\n public static List> cluster(double[][] points, int k) {\n int n = points.length;\n\n // Build complete graph with Euclidean distances\n List edges = new ArrayList<>();\n for (int i = 0; i < n; i++) {\n for (int j = i + 1; j < n; j++) {\n double dist = euclideanDistance(points[i], points[j]);\n edges.add(new Edge(i, j, dist));\n }\n }\n\n // Build MST\n edges.sort(Comparator.comparingDouble(e -> e.weight));\n UnionFind uf = new UnionFind(n);\n List mst = new ArrayList<>();\n\n for (Edge e : edges) {\n if (uf.union(e.from, e.to)) {\n mst.add(e);\n if (mst.size() == n - 1) break;\n }\n }\n\n // Remove k-1 longest edges\n mst.sort((a, b) -> Double.compare(b.weight, a.weight));\n\n UnionFind clusterUF = new UnionFind(n);\n for (int i = k - 1; i < mst.size(); i++) {\n Edge e = mst.get(i);\n clusterUF.union(e.from, e.to);\n }\n\n // Extract clusters\n Map> clusterMap = new HashMap<>();\n for (int i = 0; i < n; i++) {\n int root = clusterUF.find(i);\n clusterMap.computeIfAbsent(root, r -> new HashSet<>()).add(i);\n }\n\n return new ArrayList<>(clusterMap.values());\n }\n\n private static double euclideanDistance(double[] a, double[] b) {\n double sum = 0;\n for (int i = 0; i < a.length; i++) {\n sum += Math.pow(a[i] - b[i], 2);\n }\n return Math.sqrt(sum);\n }\n\n record Edge(int from, int to, double weight) {}\n}\n```\n\n### Network Design with Steiner Tree Approximation\n\n```java\npublic class SteinerTreeApprox {\n /**\n * Approximate Steiner tree using MST.\n * Steiner tree: minimum tree connecting subset of vertices.\n *\n * 2-approximation: Build MST on terminal vertices using\n * shortest paths as edge weights.\n */\n public static int approximateSteinerTree(\n WeightedGraph graph,\n Set terminals) {\n\n // Compute all-pairs shortest paths between terminals\n Map shortestPaths = new HashMap<>();\n for (int t : terminals) {\n shortestPaths.put(t, Dijkstra.shortestPaths(graph, t));\n }\n\n // Build complete graph on terminals\n List terminalList = new ArrayList<>(terminals);\n List edges = new ArrayList<>();\n\n for (int i = 0; i < terminalList.size(); i++) {\n for (int j = i + 1; j < terminalList.size(); j++) {\n int u = terminalList.get(i);\n int v = terminalList.get(j);\n int dist = shortestPaths.get(u)[v];\n edges.add(new Kruskal.Edge(i, j, dist));\n }\n }\n\n // MST on terminal graph\n return Kruskal.mstWeight(terminals.size(), edges);\n }\n}\n```\n\n### Maximum Bottleneck Path\n\n```java\npublic class MaxBottleneckPath {\n /**\n * Find path where minimum edge weight is maximized.\n * Uses Maximum Spanning Tree property.\n */\n public static int maxBottleneck(WeightedGraph graph, int src, int dst) {\n // Build Maximum Spanning Tree\n List maxST = maximumSpanningTree(graph);\n\n // BFS/DFS on MST to find path\n Map> mstAdj = new HashMap<>();\n for (Edge e : maxST) {\n mstAdj.computeIfAbsent(e.from, k -> new ArrayList<>()).add(e);\n mstAdj.computeIfAbsent(e.to, k -> new ArrayList<>())\n .add(new Edge(e.to, e.from, e.weight));\n }\n\n // BFS to find path and minimum edge on path\n Queue queue = new LinkedList<>(); // [vertex, minEdge]\n Set visited = new HashSet<>();\n\n queue.offer(new int[]{src, Integer.MAX_VALUE});\n visited.add(src);\n\n while (!queue.isEmpty()) {\n int[] curr = queue.poll();\n int u = curr[0];\n int minSoFar = curr[1];\n\n if (u == dst) return minSoFar;\n\n for (Edge e : mstAdj.getOrDefault(u, List.of())) {\n if (!visited.contains(e.to)) {\n visited.add(e.to);\n queue.offer(new int[]{e.to, Math.min(minSoFar, e.weight)});\n }\n }\n }\n\n return -1; // No path\n }\n\n private static List maximumSpanningTree(WeightedGraph graph) {\n // Negate weights and run Kruskal's\n // Or sort edges in descending order\n // Implementation omitted for brevity\n return null;\n }\n\n record Edge(int from, int to, int weight) {}\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Union-Find Without Optimizations\n\n```java\n// ❌ No path compression - O(n) per find\npublic int findSlow(int x) {\n while (parent[x] != x) {\n x = parent[x];\n }\n return x;\n}\n\n// ✅ With path compression - O(α(n)) amortized\npublic int findFast(int x) {\n if (parent[x] != x) {\n parent[x] = find(parent[x]); // Path compression\n }\n return parent[x];\n}\n```\n\n### Mistake 2: Forgetting MST Has V-1 Edges\n\n```java\n// ❌ Might process all edges unnecessarily\nfor (Edge e : sortedEdges) {\n if (uf.union(e.from, e.to)) {\n mst.add(e);\n }\n}\n\n// ✅ Stop early when MST is complete\nfor (Edge e : sortedEdges) {\n if (uf.union(e.from, e.to)) {\n mst.add(e);\n if (mst.size() == vertices - 1) break; // MST complete!\n }\n}\n```\n\n### Mistake 3: Not Handling Disconnected Graphs\n\n```java\n// ❌ Assumes graph is connected\nList mst = kruskal(vertices, edges);\nint totalWeight = mst.stream().mapToInt(e -> e.weight).sum();\n\n// ✅ Check if MST is complete\nList mst = kruskal(vertices, edges);\nif (mst.size() < vertices - 1) {\n throw new IllegalStateException(\"Graph is not connected - no spanning tree exists\");\n}\n```\n\n### Mistake 4: Wrong Prim's Priority Queue Update\n\n```java\n// ❌ Not checking if vertex already in MST\nfor (Edge e : graph.neighbors(u)) {\n if (e.weight < key[e.to]) {\n key[e.to] = e.weight;\n pq.offer(new int[]{e.to, e.weight});\n }\n}\n\n// ✅ Check inMST before updating\nfor (Edge e : graph.neighbors(u)) {\n if (!inMST[e.to] && e.weight < key[e.to]) {\n key[e.to] = e.weight;\n parent[e.to] = u;\n pq.offer(new int[]{e.to, e.weight});\n }\n}\n```\n\n---\n\n## 🐛 Debug This: The Broken MST\n\nThese implementations have bugs. Find and fix them:\n\n```java\npublic class BrokenMST {\n\n // Bug 1: Union-Find\n class UnionFind {\n int[] parent, rank;\n\n UnionFind(int n) {\n parent = new int[n];\n rank = new int[n];\n for (int i = 0; i < n; i++) {\n parent[i] = i;\n }\n }\n\n int find(int x) {\n if (parent[x] != x) {\n find(parent[x]); // Bug\n }\n return parent[x];\n }\n\n void union(int x, int y) {\n int px = find(x), py = find(y);\n if (rank[px] < rank[py]) {\n parent[px] = py;\n } else {\n parent[py] = px;\n if (rank[px] == rank[py]) rank[px]++; // Bug\n }\n }\n }\n\n // Bug 2: Kruskal's\n List kruskal(int n, int[][] edges) {\n Arrays.sort(edges, (a, b) -> a[2] - b[2]);\n UnionFind uf = new UnionFind(n);\n List mst = new ArrayList<>();\n\n for (int[] e : edges) {\n uf.union(e[0], e[1]); // Bug\n mst.add(e);\n }\n return mst;\n }\n\n // Bug 3: Prim's\n int prim(int[][] graph) {\n int n = graph.length;\n int[] key = new int[n];\n boolean[] inMST = new boolean[n];\n Arrays.fill(key, Integer.MAX_VALUE);\n key[0] = 0;\n\n int total = 0;\n for (int i = 0; i < n; i++) {\n int u = minKey(key, inMST);\n total += key[u];\n\n for (int v = 0; v < n; v++) {\n if (graph[u][v] > 0 && graph[u][v] < key[v]) { // Bug\n key[v] = graph[u][v];\n }\n }\n inMST[u] = true; // Bug: wrong order\n }\n return total;\n }\n}\n```\n\n

💡 Hint

\n\nLook for:\n1. Missing return assignment in path compression\n2. Missing cycle check before adding edge\n3. Missing check for `inMST[px] == inMST[py]` in union\n4. Order of operations in Prim's\n\n

\n\n

✅ Solution

\n\n```java\npublic class FixedMST {\n\n // ✅ Fix 1: Union-Find with proper path compression\n class UnionFind {\n int[] parent, rank;\n\n UnionFind(int n) {\n parent = new int[n];\n rank = new int[n];\n for (int i = 0; i < n; i++) {\n parent[i] = i;\n }\n }\n\n int find(int x) {\n if (parent[x] != x) {\n parent[x] = find(parent[x]); // ✅ Assign result back!\n }\n return parent[x];\n }\n\n boolean union(int x, int y) { // ✅ Return boolean\n int px = find(x), py = find(y);\n if (px == py) return false; // ✅ Already in same set\n\n if (rank[px] < rank[py]) {\n parent[px] = py;\n } else if (rank[px] > rank[py]) { // ✅ Fix comparison\n parent[py] = px;\n } else {\n parent[py] = px;\n rank[px]++;\n }\n return true;\n }\n }\n\n // ✅ Fix 2: Kruskal's with cycle check\n List kruskal(int n, int[][] edges) {\n Arrays.sort(edges, (a, b) -> a[2] - b[2]);\n UnionFind uf = new UnionFind(n);\n List mst = new ArrayList<>();\n\n for (int[] e : edges) {\n // ✅ Only add if doesn't create cycle\n if (uf.union(e[0], e[1])) {\n mst.add(e);\n if (mst.size() == n - 1) break; // ✅ Early termination\n }\n }\n return mst;\n }\n\n // ✅ Fix 3: Prim's with correct order\n int prim(int[][] graph) {\n int n = graph.length;\n int[] key = new int[n];\n boolean[] inMST = new boolean[n];\n Arrays.fill(key, Integer.MAX_VALUE);\n key[0] = 0;\n\n int total = 0;\n for (int i = 0; i < n; i++) {\n int u = minKey(key, inMST);\n inMST[u] = true; // ✅ Mark BEFORE updating neighbors\n total += key[u];\n\n for (int v = 0; v < n; v++) {\n // ✅ Check inMST[v] before updating\n if (graph[u][v] > 0 && !inMST[v] && graph[u][v] < key[v]) {\n key[v] = graph[u][v];\n }\n }\n }\n return total;\n }\n\n int minKey(int[] key, boolean[] inMST) {\n int min = Integer.MAX_VALUE, minIdx = -1;\n for (int i = 0; i < key.length; i++) {\n if (!inMST[i] && key[i] < min) {\n min = key[i];\n minIdx = i;\n }\n }\n return minIdx;\n }\n}\n```\n\n**Bugs explained:**\n\n1. **Union-Find find()**: `find(parent[x])` without assignment doesn't compress path. Must be `parent[x] = find(parent[x])`.\n\n2. **Kruskal's**: Adding every edge without checking if union succeeds creates cycles and includes edges between already-connected vertices.\n\n3. **Prim's**: Must mark `inMST[u] = true` BEFORE updating neighbors, otherwise we might update keys of vertices we just processed. Also need to check `!inMST[v]` before updating key.\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Min Cost to Connect All Points (LeetCode 1584) ⭐⭐\n\nConnect all points with minimum total Manhattan distance.\n\n```java\npublic class MinCostConnect {\n /**\n * @param points Array of [x, y] coordinates\n * @return Minimum cost to connect all points\n */\n public int minCostConnectPoints(int[][] points) {\n // Your implementation using Kruskal's or Prim's\n }\n}\n```\n\n---\n\n### Exercise 2: Number of Operations to Make Network Connected (LeetCode 1319) ⭐⭐\n\nFind minimum cables to move to connect all computers.\n\n```java\npublic class NetworkConnected {\n /**\n * @param n Number of computers\n * @param connections Array of [a, b] meaning cable between a and b\n * @return Minimum cables to move, or -1 if impossible\n */\n public int makeConnected(int n, int[][] connections) {\n // Your implementation using Union-Find\n }\n}\n```\n\n

💡 Hint

\n\nNeed at least n-1 cables. Extra cables (creating cycles) can be reused. Count components with Union-Find.\n\n

\n\n---\n\n### Exercise 3: Find Critical Edges in MST ⭐⭐⭐\n\nFind edges that must be in every MST and edges that can be in some MST.\n\n```java\npublic class CriticalEdges {\n /**\n * @return [critical, pseudo-critical] edge indices\n */\n public List> findCriticalAndPseudoCriticalEdges(\n int n, int[][] edges) {\n // Your implementation\n }\n}\n```\n\n---\n\n### Exercise 4: Second Minimum Spanning Tree ⭐⭐⭐⭐\n\nFind the MST with second smallest total weight.\n\n```java\npublic class SecondMST {\n /**\n * Find MST with second smallest weight.\n * May be equal to MST weight if there are multiple MSTs.\n */\n public int secondMinimumMST(int n, int[][] edges) {\n // Your implementation\n }\n}\n```\n\n

💡 Hint

\n\nFor each edge in MST, try removing it and finding MST of remaining graph. Second MST is the minimum of these attempts (plus: for each edge not in MST, try adding it and removing one edge from the cycle formed).\n\n

\n\n---\n\n### Exercise 5: Minimum Cost to Reach Destination with Stops ⭐⭐⭐⭐\n\nCombined MST and shortest path problem.\n\n```java\npublic class MinCostWithStops {\n /**\n * Build MST first, then find min cost path in MST.\n * MST guarantees minimum \"infrastructure\" cost.\n */\n public int minCost(int[][] edges, int start, int end) {\n // Your implementation\n }\n}\n```\n\n---\n\n## 🎤 Interview Questions\n\n### Question 1: When would you use Kruskal's vs Prim's?\n\n**Answer:**\n\n| Use Kruskal's when: | Use Prim's when: |\n|---------------------|------------------|\n| Sparse graph (E << V²) | Dense graph (E ≈ V²) |\n| Edges given as list | Adjacency list/matrix available |\n| Need to process edges by weight | Starting from specific vertex |\n| Already have Union-Find | Don't want Union-Find overhead |\n\n**Complexity comparison:**\n- Kruskal: O(E log E) - dominated by sorting\n- Prim (binary heap): O(E log V)\n- Prim (Fibonacci heap): O(E + V log V)\n- Prim (adjacency matrix): O(V²)\n\nFor E ≈ V²: Prim's O(V²) matrix version beats Kruskal's O(V² log V).\nFor E ≈ V: Kruskal's and Prim's are comparable.\n\n---\n\n### Question 2: Explain Union-Find optimizations\n\n**Answer:**\n\nTwo optimizations make Union-Find nearly O(1):\n\n**1. Path Compression** (in find):\n```java\nint find(int x) {\n if (parent[x] != x)\n parent[x] = find(parent[x]); // Make x point directly to root\n return parent[x];\n}\n```\nFlattens tree during find operations.\n\n**2. Union by Rank/Size** (in union):\n```java\nvoid union(int x, int y) {\n int px = find(x), py = find(y);\n if (rank[px] < rank[py])\n parent[px] = py; // Attach smaller under larger\n else if (rank[px] > rank[py])\n parent[py] = px;\n else {\n parent[py] = px;\n rank[px]++;\n }\n}\n```\nKeeps trees balanced.\n\n**Combined complexity:** O(α(n)) per operation, where α is inverse Ackermann function. For all practical n, α(n) ≤ 4.\n\n---\n\n### Question 3: How would you find if an edge is in MST?\n\n**Answer:**\n\nTwo approaches:\n\n**Method 1: Cut Property**\nFor edge (u,v), check if it's the minimum edge crossing some cut containing u on one side and v on the other.\n\n**Method 2: Cycle Property**\nFor edge (u,v) with weight w:\n1. Remove edge (u,v) from graph\n2. Find path from u to v\n3. If all edges on path have weight < w, edge is NOT in any MST\n4. If path has edge with weight > w, edge IS in some MST\n\n**Method 3: Build MST and Check**\n1. Build MST using Kruskal's\n2. For edge not in MST: add it (creates cycle), check if it's max in cycle\n3. If it's the unique max, it's not in any MST\n4. If tied for max, it could be in some MST\n\n---\n\n### Question 4: What are MST applications beyond network design?\n\n**Answer:**\n\n1. **Clustering**: Single-linkage clustering removes k-1 longest MST edges for k clusters\n\n2. **Image segmentation**: Pixels as vertices, edge weights = difference. MST finds natural boundaries.\n\n3. **Approximation algorithms**: MST gives 2-approximation for Traveling Salesman (metric TSP)\n\n4. **Taxonomy**: Phylogenetic trees in biology\n\n5. **Circuit design**: Minimum wire length for connecting components\n\n6. **Bottleneck paths**: MST contains maximum-bottleneck path between any two vertices\n\n7. **Maze generation**: Random MST on grid creates perfect maze\n\n---\n\n### Question 5: How do you handle MST with multiple edge weight ties?\n\n**Answer:**\n\nWhen edges have equal weights:\n\n1. **MST may not be unique**: Multiple valid MSTs with same total weight\n\n2. **Kruskal's behavior**: Among equal-weight edges, order is implementation-dependent (stable sort preserves input order)\n\n3. **Finding all MSTs**: Replace each tied edge with alternatives and enumerate\n\n4. **Critical vs pseudo-critical edges**:\n - Critical: Must be in every MST\n - Pseudo-critical: In some but not all MSTs\n - Neither: In no MST\n\n```java\n// Check if edge e is critical\nboolean isCritical(int n, int[][] edges, int[] e) {\n // Build MST without e\n int mstWithout = buildMSTExcluding(n, edges, e);\n // Build MST including e\n int mstWith = buildMSTIncluding(n, edges, e);\n\n return mstWithout > mstWith; // MST worse without e\n}\n```\n\n---\n\n## 📋 Quick Reference\n\n### Union-Find Template\n\n```java\nclass UnionFind {\n int[] parent, rank;\n\n UnionFind(int n) {\n parent = new int[n];\n rank = new int[n];\n for (int i = 0; i < n; i++) parent[i] = i;\n }\n\n int find(int x) {\n if (parent[x] != x) parent[x] = find(parent[x]);\n return parent[x];\n }\n\n boolean union(int x, int y) {\n int px = find(x), py = find(y);\n if (px == py) return false;\n if (rank[px] < rank[py]) { int t = px; px = py; py = t; }\n parent[py] = px;\n if (rank[px] == rank[py]) rank[px]++;\n return true;\n }\n}\n```\n\n### Kruskal's Template\n\n```java\nint kruskal(int n, int[][] edges) {\n Arrays.sort(edges, (a,b) -> a[2] - b[2]);\n UnionFind uf = new UnionFind(n);\n int total = 0, count = 0;\n\n for (int[] e : edges) {\n if (uf.union(e[0], e[1])) {\n total += e[2];\n if (++count == n - 1) break;\n }\n }\n return count == n - 1 ? total : -1; // -1 if not connected\n}\n```\n\n### Prim's Template\n\n```java\nint prim(List[] graph) {\n int n = graph.length;\n boolean[] inMST = new boolean[n];\n PriorityQueue pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);\n pq.offer(new int[]{0, 0});\n int total = 0;\n\n while (!pq.isEmpty()) {\n int[] curr = pq.poll();\n int u = curr[0], w = curr[1];\n if (inMST[u]) continue;\n inMST[u] = true;\n total += w;\n\n for (int[] e : graph[u]) {\n if (!inMST[e[0]]) pq.offer(new int[]{e[0], e[1]});\n }\n }\n return total;\n}\n```\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| Day 1 | Read article, implement Union-Find | 60 min |\n| Day 3 | Implement Kruskal's from scratch | 30 min |\n| Day 7 | Implement Prim's with priority queue | 30 min |\n| Day 14 | Solve MST LeetCode problems | 45 min |\n| Day 30 | Review and implement clustering | 20 min |\n\n---\n\n## 🔗 What's Next?\n\n**Part 14: Advanced Graph Algorithms** covers:\n- Strongly Connected Components (Tarjan, Kosaraju)\n- Articulation points and bridges\n- Max flow (Ford-Fulkerson, Edmonds-Karp)\n- Bipartite matching\n\n**Key insight preview**: These algorithms reveal deep graph structure - which vertices/edges are critical, how information flows, and how to optimally match elements.\n\n---\n\n*This article is part of the Algorithms Compendium series. For the complete learning path, see Part 0: How to Use This Series.*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.199258Z","createdAt","2026-06-10T07:19:25.200013Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",22,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",13,"author",{"_31":55,"_103":57,"_104":105,"_106":107,"_108":-5,"_109":-5,"_110":-5,"_111":-5,"_112":-5},"category",{"_31":99,"_73":59,"_35":100,"_76":101,"_102":-5},"tags",[79,80,81,82,83],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":96,"_73":97,"_35":98},{"_31":93,"_73":94,"_35":95},{"_31":90,"_73":91,"_35":92},{"_31":87,"_73":88,"_35":89},{"_31":84,"_73":85,"_35":86},173,"Union-find","union-find",172,"Prim","prim",174,"Network Design","network-design",170,"Mst","mst",171,"Kruskal","kruskal",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]