Kruskal MST — Duplicate Edges Cause V-2 Edge Count

Network infrastructure engineers don't debate Kruskal vs Prim at a whiteboard for fun — they debate it because the wrong choice can tank performance on a graph with a million edges. MST algorithms power cable laying, circuit board routing, cluster analysis in machine learning, image segmentation, and approximation algorithms for NP-hard problems like TSP. If you've ever wondered how Spotify groups similar songs or how Cisco routes OSPF traffic, MSTs are lurking in the background.

The core problem MST solves is deceptively simple: given a connected, weighted, undirected graph, find the subset of edges that keeps the graph connected, contains no cycle, and has the minimum possible total edge weight. That subset is always a tree (N nodes, N-1 edges). The real challenge is doing this efficiently at scale — a naive approach checking all spanning trees is factorial in complexity, which is completely unusable in production.

By the end of this article you'll understand not just how both algorithms work, but why they're correct (the cut property and cycle property of MSTs), when each one dominates the other in practice, how Union-Find with path compression makes Kruskal fly, how a priority queue shapes Prim's performance, and exactly what breaks in each algorithm when your graph has duplicate edge weights, disconnected components, or negative weights.

What is Minimum Spanning Tree? — Plain English

A Minimum Spanning Tree (MST) is a subset of edges in a connected, undirected, weighted graph that: (1) connects all nodes, (2) contains no cycles, and (3) has the minimum possible total edge weight.

Real-world analogy: a telephone company wants to lay cables connecting 10 cities. They want every city reachable from every other city, and they want to minimize the total cable length. The MST gives the exact set of cables to lay. Two classic algorithms solve MST: Kruskal's (sort edges, add cheapest that doesn't form a cycle) and Prim's (grow a tree greedily from one node, always adding the cheapest edge connecting the tree to a new node).

How Minimum Spanning Tree Works — Step by Step

Kruskal's Algorithm: 1. Sort all edges by weight in ascending order. 2. Initialize a Union-Find data structure where each node is its own component. 3. For each edge (u, v, w) in sorted order: a. If u and v are in different components (find(u) != find(v)), add this edge to the MST. b. Union the two components (union(u, v)). c. Stop when the MST has V-1 edges.

Prim's Algorithm (min-heap version): 1. Start from any node. Mark it visited. Push all its edges into a min-heap keyed by weight. 2. While the heap is non-empty and the MST has fewer than V-1 edges: a. Pop the minimum-weight edge (w, u, v). b. If v is already in the MST, skip (this edge would form a cycle). c. Add v to the MST. Add edge (u,v,w) to results. Push all edges from v to unvisited nodes.

Both algorithms produce the same MST (or an equally-weighted one). Time: O(E log E) for Kruskal's, O(E log V) for Prim's with a heap.

Worked Example — Tracing the Algorithm

Graph with 5 nodes (A-E) and edges: A-B:2, A-C:3, B-C:1, B-D:4, C-E:5, D-E:1

Kruskal's trace (edges sorted by weight): Sorted edges: B-C:1, D-E:1, A-B:2, A-C:3, B-D:4, C-E:5

Step 1: B-C:1 — B and C are in different components. Add to MST. Union(B,C). MST={B-C} Step 2: D-E:1 — D and E are in different components. Add to MST. Union(D,E). MST={B-C, D-E} Step 3: A-B:2 — A and B are in different components. Add to MST. Union(A,B,C). MST={B-C, D-E, A-B} Step 4: A-C:3 — A and C are in the SAME component. SKIP (would form cycle A-B-C). Step 5: B-D:4 — B is in {A,B,C}, D is in {D,E}. Add to MST. Union all. MST={B-C, D-E, A-B, B-D} MST has 4 edges = V-1 = 5-1. Done.

Total MST weight: 1+1+2+4 = 8 The edge C-E:5 was not needed — the path C-B-D-E achieves connectivity for less total cost.

Visual Step-by-Step of Kruskal Edge Selection

The following diagram visualizes the edge selection process for the 5-node graph from the worked example. Each row shows the current state of edges (processed and added) during a step. Highlighted indices indicate the edge under consideration, and the note explains the decision.

Real-World Applications of Minimum Spanning Trees

MST algorithms are not just academic; they power real infrastructure and data analysis pipelines:

• Network Design: Laying fiber optic cables, electrical grids, or water pipelines — MST gives the cheapest layout that connects all endpoints.
• Cluster Analysis: In machine learning, MST-based clustering (e.g., single-linkage hierarchical clustering) builds a spanning tree of data points and cuts the heaviest edges to form clusters. Spotify's song similarity groups use MST-based techniques.
• Image Segmentation: In computer vision, MST segments an image by treating pixels as nodes and edge weights as color/intensity differences. The MST groups similar pixels while separating dissimilar ones — widely used in medical imaging.
• Approximation Algorithms: MST is the backbone of the 2-approximation for the Traveling Salesman Problem (TSP) and helps solve Steiner tree problems.
• Circuit Design: Routing traces on a PCB—MST minimizes total track length while ensuring connectivity.
• Social Network Analysis: Finding communities in graphs by building the MST and removing low-correlation edges.

Implementation — Kruskal's Algorithm in Python

kruskal sorts all edges by weight then processes them with Union-Find. find uses iterative path halving for efficiency. union attaches by rank. An edge is added to the MST only when it connects two different components. The loop stops early once the MST has n-1 edges, avoiding unnecessary edge processing.

def kruskal(n, edges):
    """n = number of nodes (0..n-1), edges = list of (weight, u, v)"""
    edges.sort()
    parent = list(range(n))
    rank   = [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb: return False
        if rank[ra] < rank[rb]: ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1
        return True

    mst = []
    for w, u, v in edges:
        if union(u, v):
            mst.append((u, v, w))
            if len(mst) == n - 1:
                break
    return mst

# Node mapping: A=0,B=1,C=2,D=3,E=4
edges = [(2,0,1),(3,0,2),(1,1,2),(4,1,3),(5,2,4),(1,3,4)]
mst = kruskal(5, edges)
names = 'ABCDE'
total = sum(w for _,_,w in mst)
for u,v,w in mst:
    print(f'{names[u]}-{names[v]}: {w}')
print(f'Total MST weight: {total}')

Implementation — Kruskal's Algorithm in C++

Below is a production-grade C++ implementation of Kruskal's algorithm using a custom struct for edges, std::sort, and an inline Disjoint Set Union (DSU) class with path compression and union by size. The code reads from a vector of edges, sorts by weight, and processes them with the DSU. The MST edges are collected in a result vector. The main function demonstrates the same 5-node graph.

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& o) const { return w < o.w; }
};

struct DSU {
    vector<int> parent, sz;
    DSU(int n) : parent(n), sz(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path compression
            x = parent[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

vector<Edge> kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    vector<Edge> mst;
    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            mst.push_back(e);
            if (mst.size() == n - 1) break;
        }
    }
    return mst;
}

int main() {
    vector<Edge> edges = {
        {0,1,2}, {0,2,3}, {1,2,1}, {1,3,4}, {2,4,5}, {3,4,1}
    };
    auto mst = kruskal(5, edges);
    int total = 0;
    for (auto& e : mst) {
        cout << (char)('A'+e.u) << '-' << (char)('A'+e.v) << ": " << e.w << '\n';
        total += e.w;
    }
    cout << "Total MST weight: " << total << '\n';
    return 0;
}

Implementation — Prim's Algorithm in Java

Prim's algorithm uses a min-priority queue of edges (or vertices). The adjacency list is built as a map from node to list of (neighbor, weight). We start from node 0, mark it visited, and push all its edges. While the heap has edges and MST not complete, we pop the cheapest edge. If the target node is already visited, skip. Otherwise, add to MST and push its unvisited neighbors.

Java implementation uses a custom Edge class and PriorityQueue with comparator.

package io.thecodeforge.mst;

import java.util.*;

public class PrimMST {
    static class Edge implements Comparable<Edge> {
        int to, weight;
        Edge(int t, int w) { to = t; weight = w; }
        public int compareTo(Edge o) { return Integer.compare(this.weight, o.weight); }
    }

    public static List<int[]> prim(int n, List<List<Edge>> adj) {
        boolean[] visited = new boolean[n];
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        List<int[]> mst = new ArrayList<>();

        visited[0] = true;
        for (Edge e : adj.get(0)) pq.offer(e);

        while (!pq.isEmpty() && mst.size() < n - 1) {
            Edge cur = pq.poll();
            if (visited[cur.to]) continue;
            visited[cur.to] = true;
            mst.add(new int[]{cur.to, cur.weight});
            for (Edge e : adj.get(cur.to)) {
                if (!visited[e.to]) pq.offer(e);
            }
        }
        return mst;
    }

    public static void main(String[] args) {
        int n = 5;
        List<List<Edge>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        // add edges: A=0,B=1,C=2,D=3,E=4
        adj.get(0).add(new Edge(1,2)); adj.get(1).add(new Edge(0,2));
        adj.get(0).add(new Edge(2,3)); adj.get(2).add(new Edge(0,3));
        adj.get(1).add(new Edge(2,1)); adj.get(2).add(new Edge(1,1));
        adj.get(1).add(new Edge(3,4)); adj.get(3).add(new Edge(1,4));
        adj.get(2).add(new Edge(4,5)); adj.get(4).add(new Edge(2,5));
        adj.get(3).add(new Edge(4,1)); adj.get(4).add(new Edge(3,1));

        List<int[]> mst = prim(n, adj);
        int total = 0;
        for (int[] e : mst) total += e[1];
        System.out.println("MST weight: " + total);
    }
}

When to Use Kruskal vs Prim — Decision Framework

Choosing between Kruskal and Prim is a trade-off based on graph density and edge distribution:

• Sparse graphs (E ≈ V): Kruskal wins because sorting O(E log E) is dominated by E, and Union-Find operations are near-constant. Prim's heap overhead (O(E log V)) has a log factor on V but E is small.
• Dense graphs (E ≈ V^2): Prim with a Fibonacci heap outruns Kruskal because heap operations are O(E + V log V) vs O(E log E) for Kruskal.
• Very large graphs (millions of edges): Kruskal's sorting memory can be a bottleneck. Prim's adjacency list also memory-heavy, but you can stream edges from disk for Kruskal using external sorting.
• Graph with near-duplicate edge weights: Kruskal handles ties naturally (any order works). Prim's heap might need tie-breaking stabilisation.

Advantages and Disadvantages of MST Algorithms

Both Kruskal and Prim have strengths and weaknesses. The table below helps you decide which suits your constraints.

Borůvka's Algorithm — The Third Classic MST

Borůvka's algorithm is the oldest MST algorithm (1926) and the only one that naturally parallelizes across graph partitions. It works in phases: 1. Each node selects the cheapest edge incident to it. 2. All selected edges are added to the MST (they are safe by cut property). 3. The graph is contracted by merging components connected by added edges. 4. Repeat until only one component remains (V-1 edges).

Each phase runs in O(E) time, and the number of phases is O(log V) because the number of components at least halves. Total time O(E log V) without needing a fancy priority queue. Borůvka's is less common in textbooks but shines in distributed systems (e.g., MapReduce) because each node's cheapest edge can be computed independently. Modern implementations for massive graphs (like Google's Pregel) use Borůvka-style approaches. If you need to compute MST on a graph too large to fit in memory, Borůvka's is your best bet.

Production Pitfalls and Edge Cases

MST algorithms seem simple but have subtle edge cases that break in production:

1. Disconnected graph: Both algorithms will produce a spanning forest (one tree per component). Kruskal will simply not add enough edges. Prim will only explore the component containing the start node. Always check final edge count == V-1, or run a connectivity check beforehand.
2. Negative edge weights: Both algorithms handle negative weights correctly — the cut property still holds. However, if you use a variant of Prim that assumes non-negative (like Dijkstra-based), you might get wrong results. Standard Prim works fine.
3. Duplicate edge weights: Multiple MSTs possible. Kruskal's sorting order among equal-weight edges is implementation-defined — different sort stability produces different trees. For deterministic output, tie-break by edge index or node IDs.
4. Integer overflow: Edge weights summed can exceed 32-bit int. Use 64-bit (long in Java, int64 in C++) for total weight. JS and Python handle big ints natively.
5. Memory explosion in Kruskal: Sorting E edges may require O(E) auxiliary memory. For graphs with tens of millions of edges, use external sort or switch to Prim.

Practice Problems to Master MST

The best way to solidify MST concepts is to solve real problems. Below are curated practice problems from popular judges, ranging from basic implementation to advanced variations. Start with the easy ones (simple Kruskal) and move to harder ones (MST with constraints, second-best MST, dynamic MST).

Why Your Distributed System Will Fail Without MST: Network Partitioning & You

Most devs think MST is a homework problem. They're dead wrong. In production, you build overlay networks for data centers, mesh networks for IoT, or multicast trees for streaming. The naive approach — connect everything to the cheapest switch — guarantees a loop nightmare. Broadcast storms kill availability. MST gives you the minimal set of edges that keep every node reachable without cycles. That's the 'spanning' guarantee. The 'minimum' part saves you money on cables, switches, and latency. Here's the real-world WHY: when a link goes down in your distributed system, you need a precomputed backup tree. MST provides that backbone. You don't renegotiate connections mid-crash. You failover to the next-best minimum spanning tree. Every datacenter networking engineer I know has a MST algorithm in their back pocket. Not because exams, but because 3 AM pages about routing loops hurt.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class NetworkOverlayBuilder {
    static class Edge implements Comparable<Edge> {
        int src, dst, latencyMs;
        Edge(int s, int d, int l) { src=s; dst=d; latencyMs=l; }
        public int compareTo(Edge o) { return Integer.compare(latencyMs, o.latencyMs); }
    }

    // Returns minimal latency spanning tree for 5 data-center nodes
    public static List<Edge> buildMinLatencyOverlay(int nodeCount, List<Edge> allLinks) {
        Collections.sort(allLinks);
        int[] parent = new int[nodeCount];
        for (int i = 0; i < nodeCount; i++) parent[i] = i;
        List<Edge> treeEdges = new ArrayList<>();

        for (Edge e : allLinks) {
            int rootSrc = find(parent, e.src);
            int rootDst = find(parent, e.dst);
            if (rootSrc != rootDst) {
                treeEdges.add(e);
                parent[rootSrc] = rootDst;  // union — no cycle
            }
        }
        return treeEdges;
    }

    private static int find(int[] parent, int node) {
        while (parent[node] != node) node = parent[node];
        return node;
    }

    public static void main(String[] args) {
        List<Edge> links = Arrays.asList(
            new Edge(0,1,10), new Edge(0,2,15), new Edge(1,2,5),
            new Edge(1,3,20), new Edge(2,3,30), new Edge(3,4,8));
        List<Edge> overlay = buildMinLatencyOverlay(5, links);
        for (Edge e : overlay)
            System.out.println(e.src + "-" + e.dst + " lat=" + e.latencyMs);
    }
}

MST vs Shortest Path: The Mistake That Kills Your Cloud Bill

Confusing MST with Dijkstra's shortest path is a rite of passage — and a costly one. Shortest path gives you the minimal distance from point A to point B. MST gives you the minimal set of edges that connect every node. They solve different problems. But here's the trap: people use MST to build routing tables. Don't. MST doesn't care about node-to-node optimality. It only cares about total global weight. If you need every host to have a low-latency path to a single origin (like a streaming server), use shortest-path trees. If you need to wire up a warehouse full of sensors so every device can talk to every other device, use MST. The wrong choice leads to oversubscribed links and angry finance teams. I've seen a team run Kruskal on a mesh network, then wonder why their video feeds buffer. They built a cheap network, not a fast one. Two different goals. Know the difference before your AWS bill arrives.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class MstVsShortestPath {
    // Prim's MST for a grid of edge weights — connectivity not speed
    static int primMst(int[][] graph, int nodes) {
        boolean[] visited = new boolean[nodes];
        int[] minEdge = new int[nodes];
        Arrays.fill(minEdge, Integer.MAX_VALUE);
        minEdge[0] = 0;
        int totalWeight = 0;

        for (int i = 0; i < nodes; i++) {
            int u = -1;
            for (int j = 0; j < nodes; j++) 
                if (!visited[j] && (u == -1 || minEdge[j] < minEdge[u])) u = j;
            visited[u] = true;
            totalWeight += minEdge[u];
            for (int v = 0; v < nodes; v++) 
                if (graph[u][v] != 0 && !visited[v] && graph[u][v] < minEdge[v])
                    minEdge[v] = graph[u][v];
        }
        return totalWeight;
    }

    public static void main(String[] args) {
        int[][] grid = {
            {0, 2, 0, 6, 0},
            {2, 0, 3, 8, 5},
            {0, 3, 0, 0, 7},
            {6, 8, 0, 0, 9},
            {0, 5, 7, 9, 0}
        };
        System.out.println("MST total weight: " + primMst(grid, 5)); 
        // Shortest path (Dijkstra) from 0 to 4 would be 0->1->4 cost=7, not part of MST cost calc
    }
}

Reverse-Delete Algorithm: The MST Contrarian You Need for Edge-Case Validation

Everyone knows Kruskal and Prim. Borůvka gets a footnote. But Reverse-Delete? That's the dark horse. It starts with the full graph, sorts edges descending by weight, and removes the heaviest edge that doesn't disconnect the graph. Why should you care? Because it's the perfect sanity check for your MST implementation. Reverse-Delete and Kruskal must produce the same total weight (though not necessarily the same edge set — multiple MSTs exist). If they don't, you've got a bug in your union-find or your priority queue. I've literally caught off-by-one errors in production C++ MST code by running Reverse-Delete in parallel. Also, Reverse-Delete is educational: it proves that the heaviest edge in any cycle can safely be discarded. That insight alone helps you reason about MST uniqueness. The code is dead simple — no sorting upfront, just a list and a connectedness check. Don't use it in prod for huge graphs (O(E log E + E*(V+E)) is nasty). Use it to validate, not to scale.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class ReverseDeleteValidator {
    static class Edge { int src, dst, weight; Edge(int s, int d, int w) { src=s; dst=d; weight=w; } }

    static int reverseDeleteMST(int nodes, List<Edge> edges) {
        edges.sort((a,b) -> b.weight - a.weight); // descending
        int total = 0;
        List<Edge> remaining = new ArrayList<>(edges);

        for (Edge e : edges) {
            remaining.remove(e);
            if (!isConnected(nodes, remaining)) remaining.add(e); // can't cut this
        }
        for (Edge e : remaining) total += e.weight;
        return total;
    }

    static boolean isConnected(int n, List<Edge> edges) {
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (Edge e : edges) { adj[e.src].add(e.dst); adj[e.dst].add(e.src); }
        boolean[] visited = new boolean[n];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0); visited[0] = true;
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v : adj[u]) if (!visited[v]) { visited[v]=true; stack.push(v); }
        }
        for (boolean v : visited) if (!v) return false;
        return true;
    }

    public static void main(String[] args) {
        List<Edge> edges = Arrays.asList(
            new Edge(0,1,4), new Edge(0,2,3), new Edge(1,2,1), new Edge(1,3,2), new Edge(2,3,5));
        System.out.println("Reverse-Delete MST weight: " + reverseDeleteMST(4, edges));
    }
}

Why Union-Find Makes or Breaks Your Kruskal's — The Real Bottleneck

Most engineers think Kruskal's is just sorting edges and picking them. That's the easy part. The hard part — the part that crashes your production system — is how you check for cycles.

Naively, you'd do a DFS from each vertex every time you add an edge. That's O(E * V). On a graph with 100k nodes and 1M edges, that's not just slow, it's a cluster failure waiting to happen.

Union-Find (Disjoint Set Union) drops cycle detection to nearly O(α(n)) per operation — essentially constant time. The trick is path compression and union by rank. Without these, your Union-Find degenerates into a linked list and you're back to O(V) per check.

Always implement Union-Find with both optimizations. Test it on a sparse, dense, and disconnected graph before deploying. The 15 minutes you spend writing it right saves you a 3-hour debugging session at 2 AM.

// io.thecodeforge — dsa tutorial

class UnionFind {
    int[] parent, rank;

    UnionFind(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 rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[rx] > rank[ry]) parent[ry] = rx;
        else { parent[ry] = rx; rank[rx]++; }
        return true;
    }
}

MST in Distributed Systems: The Network Consensus You Can't Afford to Get Wrong

You think MST is just a textbook algorithm. Then your distributed microservice cluster grows to 500 nodes, and suddenly your service mesh is routing traffic through 15 hops when 3 would do. That's your cloud bill ballooning because nobody ran a distributed MST.

In distributed systems, every node runs a local copy of the algorithm without global knowledge. The Gallager-Humblet-Spira (GHS) algorithm solves this — it's Prim's for the distributed world. Each node holds fragments, merges them via minimum-weight outgoing edges, and converges without a central coordinator.

The gotcha: nodes must agree on edge weights. If two nodes see different costs for the same link, your MST forks into impossible topologies. Use a consistent hashing scheme or a shared config store for weights. Clock skew kills convergence — implement Lamport timestamps or logical clocks.

Before scaling beyond 100 nodes, simulate the MST convergence with random network partitions. Half your nodes going dark should not cause a routing loop. It will if you didn't handle edge case stability.

// io.thecodeforge — dsa tutorial

import java.util.*;

class DistributedMSTNode {
    int id, level = 0;
    String fragmentName = String.valueOf(id);
    List<Edge> localEdges = new ArrayList<>();
    DistributedMSTNode bestEdge = null;
    boolean inMST = false;

    void processMessages() {
        // GHS phase: find minimum weight outgoing edge
        Edge minEdge = localEdges.stream()
            .min(Comparator.comparingInt(e -> e.weight))
            .orElse(null);
        if (minEdge != null) {
            bestEdge = minEdge.neighbor;
        }
    }

    record Edge(int weight, DistributedMSTNode neighbor) {}
}