DSA Tutorial

🌉 Kruskal's Algorithm in DSA (Using C)

Kruskal’s Algorithm helps in finding the Minimum Spanning Tree (MST) of a graph by choosing the edges with the smallest weights first (Greedy approach).

🔧 How It Works:

• Sort all edges in non-decreasing order of weight.
• Pick the smallest edge. If it doesn’t form a cycle, include it in MST.
• Repeat until MST includes (V-1) edges.

🧪 C Program for Kruskal’s Algorithm

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

#define V 5 // Number of vertices

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

// Compare function for qsort
int compare(const void* a, const void* b) {
    return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}

int parent[V];

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

// Union function
void unionSet(int x, int y) {
    int xroot = find(x);
    int yroot = find(y);
    parent[xroot] = yroot;
}

void KruskalMST(struct Edge edges[], int E) {
    struct Edge result[V]; // Store MST
    int e = 0; // Count of edges in MST
    int i = 0;

    for (int v = 0; v < V; v++)
        parent[v] = v;

    qsort(edges, E, sizeof(edges[0]), compare);

    while (e < V - 1 && i < E) {
        struct Edge next = edges[i++];
        int x = find(next.src);
        int y = find(next.dest);

        if (x != y) {
            result[e++] = next;
            unionSet(x, y);
        }
    }

    printf("Edge \tWeight\n");
    int total = 0;
    for (i = 0; i < e; i++) {
        printf("%d - %d \t%d\n", result[i].src, result[i].dest, result[i].weight);
        total += result[i].weight;
    }
    printf("Total Cost of MST: %d\n", total);
}

int main() {
    struct Edge edges[] = {
        {0, 1, 10}, {0, 2, 6}, {0, 3, 5},
        {1, 3, 15}, {2, 3, 4}
    };

    int E = sizeof(edges) / sizeof(edges[0]);
    KruskalMST(edges, E);

    return 0;
}
  

📤 Output Example

Edge    Weight
2 - 3   4
0 - 3   5
0 - 1   10
Total Cost of MST: 19