Kruskal's Algorithm - Minimum Spanning Tree

Kruskal's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted, connected, and undirected graph. Unlike Prim's algorithm (which grows a tree from a single vertex), Kruskal's algorithm builds the MST one edge at a time by adding the cheapest edges that do not form a cycle.

Think of it like a smart shopper who wants to buy cables to connect all cities. You sort all available cables by price (cheapest first) and buy them one by one. However, you refuse to buy a cable that connects two cities that are already connected indirectly, because that would create a loop (wasting money). You keep buying until all cities are connected.

Key Properties

• Greedy algorithm (makes the locally optimal choice at each step).
• Works only for connected, undirected, and weighted graphs.
• Uses Union-Find (Disjoint Set) data structure to detect cycles efficiently.
• The MST is unique if all edge weights are distinct.

How Kruskal's Algorithm Works (Step-by-Step)

1. Sort Edges: Sort all edges in the graph in non-decreasing order of weight (cheapest first).
2. Initialize: Create a forest where each vertex is its own tree (i.e., V separate components).
3. Iterate: For each edge (u, v) in sorted order:
   • Check if adding this edge creates a cycle.
   • To check this, use Union-Find: find the root of u and the root of v.
   • If u and v belong to different components, add the edge to the MST and union the two components.
   • If u and v belong to the same component, skip the edge (it would form a cycle).
4. Stop: Repeat until the MST has exactly V-1 edges.

Detailed Example

Consider the following weighted undirected graph:

         (2)
    A -------- B
    | \       / |
    |  (4)  (3) |
    |   \   /   |
   (1)   C     (5)
    |   / \     |
    | (6) (7)   |
    | /     \   |
    D -------- E
         (8)

Vertices: A, B, C, D, E.

Step-by-Step Execution

Step 1: Sort all edges by weight

Step 2: Initialize Union-Find
Each vertex is its own component:

• {A}, {B}, {C}, {D}, {E}

Step 3: Process edges one by one

Stop: MST has V-1 = 4 edges.

Final MST:

    A --- B
    |     |
    D     C
          |
          E

Total Weight = 1 + 2 + 3 + 5 = 11

Algorithm for Kruskal's Algorithm

Pseudocode

Kruskal(Graph G):
    Input:  G - Weighted, connected, undirected graph
    Output: MST represented as set of edges

    Step 1: Sort edges of G in non-decreasing order by weight
    Step 2: parent = {}
    Step 3: FOR each vertex v in G DO
    Step 4:     parent[v] = v    // MakeSet
    Step 5: mst_edges = []
    Step 6: FOR each edge (u, v) in sorted_edges DO
    Step 7:     root_u = find(u)
    Step 8:     root_v = find(v)
    Step 9:     IF root_u != root_v THEN
    Step 10:        mst_edges.add(edge)
    Step 11:        union(root_u, root_v)
    Step 12:    END IF
    Step 13:    IF mst_edges.size() == V-1 THEN
    Step 14:        BREAK
    Step 15: RETURN mst_edges

Union-Find (Disjoint Set) Operations

find(u)

Finds the root/representative of the set containing u. With path compression, it flattens the tree for efficiency.

find(u):
    if parent[u] != u:
        parent[u] = find(parent[u])   // Path compression
    return parent[u]

union(u, v)

Merges the sets containing u and v. With union by rank, we attach the smaller tree under the larger one.

union(u, v):
    root_u = find(u)
    root_v = find(v)
    if rank[root_u] < rank[root_v]:
        parent[root_u] = root_v
    else if rank[root_u] > rank[root_v]:
        parent[root_v] = root_u
    else:
        parent[root_v] = root_u
        rank[root_u]++

Implementation in C

Implementation with Edge List and Union-Find

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Edge structure
typedef struct Edge {
    int src, dest, weight;
} Edge;

// Graph structure
typedef struct Graph {
    int V, E;
    Edge* edges;
} Graph;

// Subset structure for Union-Find
typedef struct Subset {
    int parent;
    int rank;
} Subset;

// Create a graph
Graph* createGraph(int V, int E) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->E = E;
    graph->edges = (Edge*)malloc(E * sizeof(Edge));
    return graph;
}

// Compare function for qsort (sort edges by weight)
int compareEdges(const void* a, const void* b) {
    Edge* e1 = (Edge*)a;
    Edge* e2 = (Edge*)b;
    return e1->weight - e2->weight;
}

// Find with path compression
int find(Subset subsets[], int i) {
    if (subsets[i].parent != i) {
        subsets[i].parent = find(subsets, subsets[i].parent);
    }
    return subsets[i].parent;
}

// Union by rank
void unionSets(Subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
    
    if (subsets[xroot].rank < subsets[yroot].rank) {
        subsets[xroot].parent = yroot;
    } else if (subsets[xroot].rank > subsets[yroot].rank) {
        subsets[yroot].parent = xroot;
    } else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

// Kruskal's Algorithm
void kruskalMST(Graph* graph) {
    int V = graph->V;
    Edge* result = (Edge*)malloc(V * sizeof(Edge));  // Store MST edges
    int e = 0;  // Index for result (number of edges added)
    int i = 0;  // Index for sorted edges
    
    // Step 1: Sort all edges by weight
    qsort(graph->edges, graph->E, sizeof(graph->edges[0]), compareEdges);
    
    // Step 2: Allocate and initialize subsets
    Subset* subsets = (Subset*)malloc(V * sizeof(Subset));
    for (int v = 0; v < V; v++) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
    
    // Step 3: Iterate through sorted edges
    while (e < V - 1 && i < graph->E) {
        Edge next_edge = graph->edges[i++];
        
        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);
        
        // If including this edge doesn't create a cycle
        if (x != y) {
            result[e++] = next_edge;
            unionSets(subsets, x, y);
        }
    }
    
    // Print the MST
    printf("Kruskal's Algorithm - Minimum Spanning Tree:\n");
    printf("Edge \t\tWeight\n");
    int totalWeight = 0;
    for (i = 0; i < e; i++) {
        printf("%d - %d \t\t%d\n", result[i].src, result[i].dest, result[i].weight);
        totalWeight += result[i].weight;
    }
    printf("Total MST Weight: %d\n", totalWeight);
    
    free(result);
    free(subsets);
}

int main() {
    int V = 5;  // Vertices: 0=A, 1=B, 2=C, 3=D, 4=E
    int E = 8;
    Graph* graph = createGraph(V, E);
    
    // Add edges (src, dest, weight)
    graph->edges[0] = (Edge){0, 1, 2};   // A-B(2)
    graph->edges[1] = (Edge){0, 2, 4};   // A-C(4)
    graph->edges[2] = (Edge){0, 3, 1};   // A-D(1)
    graph->edges[3] = (Edge){1, 2, 3};   // B-C(3)
    graph->edges[4] = (Edge){1, 4, 5};   // B-E(5)
    graph->edges[5] = (Edge){2, 3, 6};   // C-D(6)
    graph->edges[6] = (Edge){2, 4, 7};   // C-E(7)
    graph->edges[7] = (Edge){3, 4, 8};   // D-E(8)
    
    kruskalMST(graph);
    return 0;
}

Output:

Kruskal's Algorithm - Minimum Spanning Tree:
Edge            Weight
0 - 3           1
0 - 1           2
1 - 2           3
1 - 4           5
Total MST Weight: 11

Visualizing Kruskal's Algorithm (Step-by-Step Trace)

Let's trace the algorithm visually to understand how the components merge:

Initial Forest:

A    B    C    D    E

After Step 1 (A-D, 1):

A - D    B    C    E

(A and D merged)

After Step 2 (A-B, 2):

A - D    B - A    C    E
    └──────┘

(A, B, D merged)

After Step 3 (B-C, 3):

A - D    B - A    C - B
    └──────┘    └────┘

(A, B, C, D all merged)

After Step 4 (B-E, 5):

A - D    B - A    C - B    E - B
    └──────┘    └────┘    └──┘

(All vertices connected!)

Final MST:

    A --- B
    |     |
    D     C
          |
          E

Complexity Analysis

Time Complexity

• Sorting Edges: O(E log E) – dominates for sparse graphs.
• Union-Find Operations: O(α(V)) per edge, where α is the inverse Ackermann function (practically constant).
• Total Complexity: O(E log E) or O(E log V) (since E ≤ V², log E ≤ 2 log V).

Space Complexity

• O(V) for the Union-Find structure (parent and rank arrays).
• O(E) for storing the edges (input).

Advantages of Kruskal's Algorithm

1. Excellent for Sparse Graphs: When E is much smaller than V², sorting E edges is efficient.
2. Simple Cycle Detection: Union-Find makes cycle detection easy and fast.
3. Incremental: You can stop early once V-1 edges are added.
4. Works on Disconnected Graphs: It can find a spanning forest (a minimum spanning tree for each component).

Disadvantages of Kruskal's Algorithm

1. Requires Sorting: The initial sorting step can be expensive for dense graphs.
2. Not Suitable for Dense Graphs: For dense graphs (E ≈ V²), O(E log E) ≈ O(V² log V), which is worse than Prim's O(V²).
3. Complex Implementation: Union-Find with path compression and union by rank requires more code than Prim's simple visited array approach.

Prim's vs. Kruskal's: When to Use Which?

When to Use Kruskal's Algorithm

• The graph is sparse (E is much less than V²).
• You want to process edges in order (e.g., you might stop early).
• You are comfortable implementing Union-Find.

When to Use Prim's Algorithm

• The graph is dense (E is close to V²).
• You want a simple implementation (especially with adjacency matrix).
• You want to start from a specific vertex.

Real-World Applications of Kruskal's Algorithm

Practice Questions

1. Consider the following graph Edges: 0-1(4), 0-2(3), 0-3(2), 1-2(1), 1-3(5), 2-3(6). Find the MST using Kruskal's algorithm.