Kruskal's MST

Graphs O(E log E) O(V)

Builds a minimum spanning tree by adding edges in weight order, using union-find to reject cycle edges.

1/19

Put each node in its own set (badge = set root).

InvariantThe kept edges form a forest; each was the lightest edge joining two different components.

currentfrontiervisitedtree edge

kruskal.c

#define V 6
 
int parent[V];
int find(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
}
 
void kruskal(Edge edges[], int m) {
    for (int i = 0; i < V; i++) parent[i] = i;
    sortByWeight(edges, m);
 
    for (int i = 0; i < m; i++) {
        int a = find(edges[i].u), b = find(edges[i].v);
        if (a == b)
            continue;           /* same set -> cycle, skip */
        parent[a] = b;          /* union: keep this edge */
    }
}

How Kruskal's MST works

Sort all edges by weight and take them cheapest-first, skipping any edge whose endpoints are already connected (union-find detects that). Independent forests merge into one MST.

When to use it

Minimum spanning tree on sparse graphs / plain edge lists; clustering by cutting the largest edges.