Program Overview

This C program implements Kruskal’s algorithm to find the Minimum Spanning Tree (MST) of a given connected, undirected graph. The program uses the union-find data structure to efficiently manage the sets of vertices.

Program Structure

• Data Structures:
  • Edge structure to represent the edges of the graph.
  • Subset structure for union-find operations.
• Functions:
  • find() – A utility function to find the subset of an element.
  • union() – A utility function to perform union of two subsets.
  • compareEdges() – A comparison function for sorting edges.
  • kruskal() – The main function to execute Kruskal’s algorithm.

C Program

#include 
#include 

#define MAX 100

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

typedef struct {
    int parent, rank;
} Subset;

int find(Subset subsets[], int i) {
    if (subsets[i].parent != i) {
        subsets[i].parent = find(subsets, subsets[i].parent);
    }
    return subsets[i].parent;
}

void unionSets(Subset subsets[], int xroot, int yroot) {
    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++;
    }
}

int compareEdges(const void *a, const void *b) {
    return ((Edge*)a)->weight > ((Edge*)b)->weight;
}

void kruskal(Edge edges[], int V, int E) {
    qsort(edges, E, sizeof(edges[0]), compareEdges);
    Subset *subsets = (Subset*)malloc(V * sizeof(Subset));

    for (int v = 0; v < V; v++) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    printf("Edges in the Minimum Spanning Tree:\n");
    for (int i = 0; i < E; i++) {
        int x = find(subsets, edges[i].src);
        int y = find(subsets, edges[i].dest);

        if (x != y) {
            printf("%d -- %d == %d\n", edges[i].src, edges[i].dest, edges[i].weight);
            unionSets(subsets, x, y);
        }
    }
    free(subsets);
}

int main() {
    int V, E;
    printf("Enter number of vertices and edges: ");
    scanf("%d %d", &V, &E);

    Edge *edges = (Edge*)malloc(E * sizeof(Edge));
    printf("Enter edges (src, dest, weight):\n");
    for (int i = 0; i < E; i++) {
        scanf("%d %d %d", &edges[i].src, &edges[i].dest, &edges[i].weight);
    }

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

How to Run the Program

1. Copy the code into a file named kruskal.c.
2. Compile the program using gcc kruskal.c -o kruskal.
3. Run the program using ./kruskal.
4. Input the number of vertices and edges followed by the edges themselves.

Conclusion

This implementation of Kruskal’s algorithm efficiently finds the Minimum Spanning Tree of a graph using a greedy approach. The union-find data structure ensures that we can quickly find and union sets, making the algorithm effective for larger graphs.