Minimum Spanning Tree Kruskal's Algorithm in DSA C

Mental Model

Pick the smallest edges one by one without making loops until all points connect.

Analogy: Imagine connecting cities with roads. You want to build the cheapest roads so every city is reachable, but you never build a road that creates a circle of roads.

Vertices: A B C D
Edges:
A --2-- B
B --3-- C
A --1-- C
C --4-- D

Initial: No roads built
A B C D

Goal: Connect all with cheapest roads without loops

Dry Run Walkthrough

Input: Graph with vertices A, B, C, D and edges: A-C(1), A-B(2), B-C(3), C-D(4)

Goal: Build a tree connecting all vertices with minimum total edge weight without cycles

Step 1: Sort edges by weight: A-C(1), A-B(2), B-C(3), C-D(4)

Edges sorted: [A-C(1), A-B(2), B-C(3), C-D(4)]

Why: We pick edges from smallest to largest to keep total cost low

Step 2: Pick edge A-C(1), add to MST

MST edges: A-C(1)
Connected sets: {A,C}, {B}, {D}

Why: First smallest edge connects two separate sets

Step 3: Pick edge A-B(2), add to MST

MST edges: A-C(1), A-B(2)
Connected sets: {A,B,C}, {D}

Why: Edge connects B to existing set without cycle

Step 4: Consider edge B-C(3), skip because it forms a cycle in {A,B,C}

MST edges: A-C(1), A-B(2)
Connected sets: {A,B,C}, {D}

Why: Adding this edge would create a loop

Step 5: Pick edge C-D(4), add to MST

MST edges: A-C(1), A-B(2), C-D(4)
Connected sets: {A,B,C,D}

Why: Connects last vertex D without cycle

Result:

MST edges: A-C(1) -> A-B(2) -> C-D(4)
All vertices connected with minimum total cost 7

Annotated Code

DSA C

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

#define MAX_EDGES 100
#define MAX_VERTICES 100

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

// Disjoint Set Union (Union-Find) structure
int parent[MAX_VERTICES];

// Find root parent with path compression
int find(int i) {
    if (parent[i] != i)
        parent[i] = find(parent[i]); // compress path
    return parent[i];
}

// Union two sets
void union_sets(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA != rootB) {
        parent[rootB] = rootA; // attach rootB to rootA
    }
}

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

// Kruskal's algorithm
void kruskal(Edge edges[], int E, int V) {
    // Initialize disjoint sets
    for (int i = 0; i < V; i++) {
        parent[i] = i;
    }

    // Sort edges by weight
    qsort(edges, E, sizeof(Edge), compare);

    printf("Edges in MST:\n");
    int mst_weight = 0;
    int count = 0;

    for (int i = 0; i < E && count < V - 1; i++) {
        int u = edges[i].src;
        int v = edges[i].dest;

        // Check if adding this edge creates a cycle
        if (find(u) != find(v)) {
            union_sets(u, v); // union sets
            printf("%c - %c : %d\n", 'A' + u, 'A' + v, edges[i].weight);
            mst_weight += edges[i].weight;
            count++;
        }
    }
    printf("Total MST weight: %d\n", mst_weight);
}

int main() {
    // Vertices: A=0, B=1, C=2, D=3
    int V = 4;
    int E = 4;
    Edge edges[] = {
        {0, 2, 1}, // A-C
        {0, 1, 2}, // A-B
        {1, 2, 3}, // B-C
        {2, 3, 4}  // C-D
    };

    kruskal(edges, E, V);
    return 0;
}

for (int i = 0; i < V; i++) { parent[i] = i; }

Initialize each vertex as its own set

qsort(edges, E, sizeof(Edge), compare);

Sort edges by weight ascending

if (find(u) != find(v)) {

Check if edge connects two different sets to avoid cycles

union_sets(u, v);

Merge sets after adding edge to MST

printf("%c - %c : %d\n", 'A' + u, 'A' + v, edges[i].weight);

Print edge added to MST

Output

Edges in MST:

A - C : 1

A - B : 2

C - D : 4

Total MST weight: 7

Complexity Analysis

Time: O(E log E) because sorting edges dominates and union-find operations are almost O(1)

Space: O(V + E) for storing edges and parent array for union-find

vs Alternative: Compared to Prim's algorithm which can be O(E + V log V) with priority queue, Kruskal is simpler and efficient for sparse graphs

Edge Cases

Empty graph (no edges)

No edges to add, MST is empty

DSA C

for (int i = 0; i < E && count < V - 1; i++) {

Graph with single vertex

No edges needed, MST weight is zero

DSA C

for (int i = 0; i < V; i++) { parent[i] = i; }

Graph with multiple edges of same weight

Algorithm picks edges in sorted order, ties resolved by qsort order

DSA C

qsort(edges, E, sizeof(Edge), compare);

When to Use This Pattern

When you need to connect all points with minimum total cost and avoid cycles, use Kruskal's algorithm because it picks edges from smallest to largest and uses union-find to detect cycles.

Common Mistakes

Mistake: Not checking if adding an edge creates a cycle before adding it
Fix: Use union-find to check if two vertices belong to different sets before union

Mistake: Not sorting edges by weight before processing
Fix: Sort edges ascending by weight before starting to pick edges

Summary

Builds a minimum cost tree connecting all vertices without cycles by picking edges from smallest to largest.

Use when you want the cheapest way to connect all points and have the graph edges available upfront.

The key insight is to add edges in order of weight and skip those that form cycles using union-find.