Kruskal's minimum spanning tree

Connect every node with the cheapest possible set of edges. Uses union-find to avoid cycles.

Time O(E log E)Space O(V)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Consider edges from cheapest to most expensive. Take an edge if it joins two separate groups of nodes. Skip it if both ends are already in the same group, because that would make a loop.

Code

C++PythonC#

struct Edge { char u, v; int w; };

vector<Edge> kruskal(vector<Edge> edges, UnionFind& uf) {
    vector<Edge> tree;
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; });
    for (const Edge& e : edges) {
        if (uf.find(e.u) == uf.find(e.v)) continue; // would close a cycle
        uf.unite(e.u, e.v);
        tree.push_back(e);
    }
    return tree;
}

def kruskal(edges: list[tuple[str, str, int]], uf: UnionFind) -> list[tuple[str, str, int]]:
    tree = []
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if uf.find(u) == uf.find(v): continue  # would close a cycle
        uf.union(u, v)
        tree.append((u, v, w))
    return tree

public static List<(char, char, int)> Kruskal(
        List<(char u, char v, int w)> edges, UnionFind uf) {
    var tree = new List<(char, char, int)>();
    foreach (var e in edges.OrderBy(e => e.w)) {
        if (uf.Find(e.u) == uf.Find(e.v)) continue; // would close a cycle
        uf.Union(e.u, e.v);
        tree.Add(e);
    }
    return tree;
}

Tips

Union-find answers "are these two nodes already connected?" in near constant time.
A spanning tree of V nodes always has exactly V - 1 edges.

In the .NET library

There is no built-in union-find. It is about 15 lines: an int[] parent, Find with path compression, and Union by rank.