Kruskal's Algorithm : Minimum Spanning Tree

Kruskal's Algorithm

Minimum Spanning Tree

A minimum spanning tree is a crucial concept in graph theory with wide-ranging applications. Imagine a network represented as a graph, where vertices represent points (like cities or computers) and edges represent connections between them with associated costs (like distances or cable lengths). A spanning tree is a subgraph that connects all vertices without any cycles. A minimum spanning tree is a spanning tree with the lowest total edge weight. In essence, it’s the cheapest way to connect all points in the network, ensuring every point is reachable without redundant connections.

Kruskal's Algorithm

Kruskal’s algorithm is a greedy approach to finding an MST in a connected, undirected, weighted graph. The algorithm, as described in (Rayward‐Smith et al., 1991) and (Cormen et al., 2023), builds the MST by iteratively adding edges in increasing order of weight, ensuring no cycles are formed.

Algorithm:

Initialization:
- Create a disjoint-set data structure where each vertex is initially in its own set. This represents a forest of individual, unconnected vertices.
- Sort all edges in the graph by weight in non-decreasing order.
Iteration:
- For each edge (u, v) in sorted order:
  - Find the sets to which vertices u and v belong using the FIND-SET operation of the disjoint-set data structure.
  - If u and v belong to different sets (i.e., adding the edge wouldn’t create a cycle):
    - Add edge (u, v) to the MST.
    - Unite the sets containing u and v using the UNION operation, effectively merging the two connected components.
Termination: The algorithm terminates when all vertices are in the same set (i.e., the MST connects all vertices) or all edges have been considered.

Time Complexity: The complexity is dominated by the sorting of edges, which takes O(E log E) time, where E is the number of edges. Disjoint-set operations take nearly linear time, making the overall complexity O(E log E

Assignment 5. Set B a) SPPU:

Write a C program for the implementation of Kruskal’s Algorithm for minimum spanning tree.

#include <stdlib.h>

#define MAX_EDGES 100
#define MAX_VERTICES 100

// Structure to represent an edge
struct Edge {
    int src, dest, weight;
};

// Structure to represent a graph
struct Graph {
    int V, E;           // V = number of vertices, E = number of edges
    struct Edge* edges; // Array of edges
};

// Structure to represent a disjoint set
struct DisjointSet {
    int parent[MAX_VERTICES];
    int rank[MAX_VERTICES];
};

// Function to create a graph
struct Graph* createGraph(int V, int E) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edges = (struct Edge*)malloc(E * sizeof(struct Edge));
    return graph;
}

// Function to create a disjoint set
struct DisjointSet* createDisjointSet(int V) {
    struct DisjointSet* ds = (struct DisjointSet*)malloc(sizeof(struct DisjointSet));
    for (int i = 0; i < V; i++) {
        ds->parent[i] = i; // Each vertex is its own parent initially
        ds->rank[i] = 0;   // Rank is 0 initially
    }
    return ds;
}

// Function to find the set of a vertex (with path compression)
int findSet(struct DisjointSet* ds, int i) {
    if (ds->parent[i] != i) {
        ds->parent[i] = findSet(ds, ds->parent[i]); // Path compression
    }
    return ds->parent[i];
}

// Function to unite two sets (with union by rank)
void unionSets(struct DisjointSet* ds, int x, int y) {
    int xRoot = findSet(ds, x);
    int yRoot = findSet(ds, y);

    // Union by rank
    if (ds->rank[xRoot] < ds->rank[yRoot]) {
        ds->parent[xRoot] = yRoot;
    } else if (ds->rank[xRoot] > ds->rank[yRoot]) {
        ds->parent[yRoot] = xRoot;
    } else {
        ds->parent[yRoot] = xRoot;
        ds->rank[xRoot]++;
    }
}

// Comparator function to sort edges by weight
int compareEdges(const void* a, const void* b) {
    return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}

// Function to implement Kruskal's algorithm
void kruskalMST(struct Graph* graph) {
    int V = graph->V;
    struct Edge result[V]; // Array to store the MST
    int e = 0;             // Index for the result array
    int i = 0;             // Index for the sorted edges array

    // Step 1: Sort all edges in non-decreasing order of weight
    qsort(graph->edges, graph->E, sizeof(graph->edges[0]), compareEdges);

    // Step 2: Create a disjoint set
    struct DisjointSet* ds = createDisjointSet(V);

    // Step 3: Iterate through all sorted edges
    while (e < V - 1 && i < graph->E) {
        // Get the next edge
        struct Edge nextEdge = graph->edges[i++];

        // Find the sets of the two vertices of the edge
        int x = findSet(ds, nextEdge.src);
        int y = findSet(ds, nextEdge.dest);

        // If the vertices are in different sets, add the edge to the MST
        if (x != y) {
            result[e++] = nextEdge;
            unionSets(ds, x, y); // Union the two sets
        }
    }

    // Print the MST
    printf("Edges in the MST:\n");
    for (i = 0; i < e; i++) {
        printf("%d - %d \t%d\n", result[i].src, result[i].dest, result[i].weight);
    }
}

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

    struct Graph* graph = createGraph(V, E);

    printf("Enter the edges (source destination weight):\n");
    for (int i = 0; i < E; i++) {
        scanf("%d %d %d", &graph->edges[i].src, &graph->edges[i].dest, &graph->edges[i].weight);
    }

    kruskalMST(graph);

    return 0;
}