Minimum Spanning Tree Kruskal's Algorithm in DSA C - Build from Scratch

Minimum Spanning Tree using Kruskal's Algorithm

📖 Scenario: You are working as a network engineer. You need to connect several computers with cables. Each cable has a cost. Your goal is to connect all computers with the least total cost, without any loops.

🎯 Goal: Build a program in C that uses Kruskal's algorithm to find the minimum spanning tree (MST) of a given graph. The program will show which connections (edges) to use and the total cost.

📋 What You'll Learn

Create an array of edges with given weights

Create a helper array for union-find operations

Implement Kruskal's algorithm to select edges for MST

Print the edges in the MST and the total cost

💡 Why This Matters

🌍 Real World

Network design to connect computers or cities with minimum cable cost.

💼 Career

Useful for software engineers working on network optimization, infrastructure planning, or graph algorithms.

1

Create the graph edges array

Create a struct called Edge with int src, int dest, and int weight. Then create an array called edges with these 5 edges: (0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4).

DSA C

// Define struct Edge and create edges array with 5 edges
// Your code here

Hint

Use typedef struct to define Edge. Then create an array edges with 5 elements using the given values.

2

Create union-find helper arrays

Create two integer arrays called parent and rank of size 4. Initialize parent so that each element is its own parent (0 to 3). Initialize all elements of rank to 0.

DSA C

typedef struct {
    int src;
    int dest;
    int weight;
} Edge;

Edge edges[5] = {
    {0, 1, 10},
    {0, 2, 6},
    {0, 3, 5},
    {1, 3, 15},
    {2, 3, 4}
};

// Create parent and rank arrays and initialize them
// Your code here

Hint

Use a for loop from 0 to 3 to set parent[i] = i and rank[i] = 0.

3

Implement Kruskal's algorithm core logic

Write functions findParent(int node) to find the root parent with path compression, and unionSet(int u, int v) to union two sets by rank. Then write a function kruskal() that sorts edges by weight, iterates over them, and adds edges to MST if their parents differ. Store MST edges in an array result and keep track of e (count of MST edges).

DSA C

typedef struct {
    int src;
    int dest;
    int weight;
} Edge;

Edge edges[5] = {
    {0, 1, 10},
    {0, 2, 6},
    {0, 3, 5},
    {1, 3, 15},
    {2, 3, 4}
};

int parent[4];
int rank[4];

void makeSet() {
    for (int i = 0; i < 4; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}

// Write findParent, unionSet, and kruskal functions
// Your code here

Hint

Use qsort to sort edges by weight. Use findParent and unionSet to check and join sets. Add edges to result if they connect different sets.

4

Run Kruskal and print MST

In main(), call makeSet() and then kruskal() to print the MST edges and total cost.

DSA C

typedef struct {
    int src;
    int dest;
    int weight;
} Edge;

Edge edges[5] = {
    {0, 1, 10},
    {0, 2, 6},
    {0, 3, 5},
    {1, 3, 15},
    {2, 3, 4}
};

int parent[4];
int rank[4];

void makeSet() {
    for (int i = 0; i weight - edgeB->weight;
}

void kruskal() {
    Edge result[4];
    int e = 0;
    int i = 0;

    qsort(edges, 5, sizeof(Edge), compareEdges);

    while (e < 3 && i < 5) {
        Edge nextEdge = edges[i++];
        int u = findParent(nextEdge.src);
        int v = findParent(nextEdge.dest);

        if (u != v) {
            result[e++] = nextEdge;
            unionSet(u, v);
        }
    }

    printf("Edges in MST:\n");
    int totalWeight = 0;
    for (int j = 0; j < e; j++) {
        printf("%d - %d : %d\n", result[j].src, result[j].dest, result[j].weight);
        totalWeight += result[j].weight;
    }
    printf("Total cost: %d\n", totalWeight);
}

// Write main function to call makeSet and kruskal
// Your code here

Hint

Call makeSet() first to initialize sets, then call kruskal() to print the MST edges and total cost.