DSA Tutorial

🌿 Minimum Spanning Tree (MST) in DSA

A Minimum Spanning Tree (MST) of a weighted, connected, undirected graph is a tree that connects all the vertices with the minimum total edge weight and no cycles.

💡 Real-Life Analogy

Think of connecting cities with roads in a way that all cities are reachable with minimum total construction cost.

🔧 Kruskal’s Algorithm (Using C)

Sort all edges by weight and add the smallest ones to the MST, avoiding cycles. Union-Find is used to detect cycles.

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

#define MAX 30

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

struct Graph {
    int V, E;
    struct Edge* edge;
};

// Find operation
int find(int parent[], int i) {
    if (parent[i] != i)
        parent[i] = find(parent, parent[i]);
    return parent[i];
}

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

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

void KruskalMST(struct Graph* graph) {
    int V = graph->V;
    struct Edge result[MAX];
    int e = 0, i = 0;

    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), compare);

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

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

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

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

int main() {
    int V = 4, E = 5;
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = malloc(E * sizeof(struct Edge));

    graph->edge[0] = (struct Edge){0, 1, 10};
    graph->edge[1] = (struct Edge){0, 2, 6};
    graph->edge[2] = (struct Edge){0, 3, 5};
    graph->edge[3] = (struct Edge){1, 3, 15};
    graph->edge[4] = (struct Edge){2, 3, 4};

    KruskalMST(graph);
    return 0;
}
  

📌 Prim’s Algorithm (Coming Next?)

It starts from a single vertex and keeps adding the smallest adjacent edge to the MST set. Want an example in C?