Kruskal's algorithm with example

Minimum spanning tree (MST): a spanning tree of a connected, weighted, undirected graph (a tree containing all V vertices and V−1 edges) whose total edge weight is the smallest possible.

Kruskal's algorithm is a greedy method: it considers the edges in increasing order of weight and adds an edge to the forest only if it does not form a cycle.

Algorithm

KRUSKAL(G)
1. T = empty set
2. make each vertex a separate set (tree)
3. sort all edges in non-decreasing order of weight
4. for each edge (u, v) in sorted order
5.     if FIND(u) != FIND(v)        // different components, no cycle
6.         add (u, v) to T
7.         UNION(u, v)
8.     if T has V-1 edges, stop
9. return T

struct edge { int u, v, w; } e[100];
int parent[50];
int find(int x) { while (parent[x] != x) x = parent[x]; return x; }

int kruskal(int V, int E) {
    int total = 0, count = 0;
    sortEdgesByWeight(e, E);                 /* ascending */
    for (int i = 0; i < V; i++) parent[i] = i;
    for (int i = 0; i < E && count < V - 1; i++) {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b) {                         /* no cycle */
            parent[a] = b;                    /* union */
            total += e[i].w; count++;
            printf("%d-%d (%d)\n", e[i].u, e[i].v, e[i].w);
        }
    }
    return total;
}

Complexity: O(E log E), dominated by sorting the edges.

Example

Graph: A-B 2, A-C 6, A-F 7, B-D 11, C-F 3, C-E 5, D-F 9, E-F 1 (6 vertices, so the MST has 5 edges).

Five edges are chosen, so we stop.

MST edges: E-F, A-B, C-F, A-C, D-F. Minimum cost = 21.