Kruskal's MST on graph A to G

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.

Application to the given graph

Edges: A-B 10, A-F 3, A-G 2, B-G 3, B-C 5, F-G 8, F-E 8, G-E 5, G-C 9, G-D 8, E-D 7, C-D 3 (7 vertices, so the MST has 6 edges).

Sorted: A-G 2, A-F 3, B-G 3, C-D 3, B-C 5, G-E 5, E-D 7, F-G 8, F-E 8, G-D 8, G-C 9, A-B 10.

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