{"id":616,"date":"2024-10-10T10:52:35","date_gmt":"2024-10-10T05:22:35","guid":{"rendered":"https:\/\/codexplained.in\/?p=616"},"modified":"2025-11-24T16:00:24","modified_gmt":"2025-11-24T10:30:24","slug":"implement-kruskals-algorithm","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=616","title":{"rendered":"Implementation of Kruskal\u2019s Algorithm"},"content":{"rendered":"\n

Understanding Kruskal\u2019s Algorithm<\/h3>\n\n\n\n

Kruskal\u2019s algorithm is a greedy algorithm that finds the minimum spanning tree for a connected, weighted graph. The steps involved are:<\/p>\n\n\n\n

    \n
  1. Sort All Edges<\/strong>: Begin by sorting all the edges in non-decreasing order of their weights.<\/li>\n\n\n\n
  2. Initialize a Forest<\/strong>: Start with an empty forest, which will grow into the minimum spanning tree.<\/li>\n\n\n\n
  3. Add Edges<\/strong>: For each edge in the sorted list, add it to the forest if it doesn\u2019t create a cycle. This is typically checked using a Union-Find data structure.<\/li>\n\n\n\n
  4. Repeat Until MST is Complete<\/strong>: Continue adding edges until there are V\u22121V – 1V\u22121 edges in the tree (where VVV is the number of vertices).<\/li>\n<\/ol>\n\n\n
    \n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX 100\n\n\/\/ Structure to represent an edge\nstruct Edge {\n    int src, dest, weight;\n};\n\n\/\/ Structure to represent a subset for union-find\nstruct Subset {\n    int parent;\n    int rank;\n};\n\n\/\/ Function to compare two edges (for qsort)\nint compare(const void* a, const void* b) {\n    struct Edge* edge1 = (struct Edge*)a;\n    struct Edge* edge2 = (struct Edge*)b;\n    return edge1->weight - edge2->weight;\n}\n\n\/\/ Find function for union-find\nint find(struct Subset subsets[], int i) {\n    if (subsets[i].parent != i) {\n        subsets[i].parent = find(subsets, subsets[i].parent);\n    }\n    return subsets[i].parent;\n}\n\n\/\/ Union function for union-find\nvoid unionSubsets(struct Subset subsets[], int x, int y) {\n    int xroot = find(subsets, x);\n    int yroot = find(subsets, y);\n\n    if (subsets[xroot].rank < subsets[yroot].rank) {\n        subsets[xroot].parent = yroot;\n    } else if (subsets[xroot].rank > subsets[yroot].rank) {\n        subsets[yroot].parent = xroot;\n    } else {\n        subsets[yroot].parent = xroot;\n        subsets[xroot].rank++;\n    }\n}\n\n\/\/ Function to implement Kruskal's algorithm\nvoid kruskal(struct Edge edges[], int V, int E) {\n    struct Edge result[MAX]; \/\/ To store the resulting MST\n    struct Subset subsets[MAX];\n\n    \/\/ Step 1: Sort all edges\n    qsort(edges, E, sizeof(edges[0]), compare);\n\n    \/\/ Create V subsets with single elements\n    for (int v = 0; v < V; ++v) {\n        subsets[v].parent = v;\n        subsets[v].rank = 0;\n    }\n\n    int e = 0; \/\/ Index variable for result\n    int i = 0; \/\/ Index variable for sorted edges\n    while (e < V - 1 && i < E) {\n        \/\/ Step 2: Pick the smallest edge\n        struct Edge nextEdge = edges[i++];\n\n        \/\/ Find the subsets of the vertices of the edge\n        int x = find(subsets, nextEdge.src);\n        int y = find(subsets, nextEdge.dest);\n\n        \/\/ If they are in different subsets, include this edge in the result\n        if (x != y) {\n            result[e++] = nextEdge;\n            unionSubsets(subsets, x, y);\n        }\n    }\n\n    \/\/ Print the resulting MST\n    printf("Edges in the Minimum Spanning Tree (Kruskal's Algorithm):\\n");\n    for (i = 0; i < e; ++i) {\n        printf("%d -- %d == %d\\n", result[i].src, result[i].dest, result[i].weight);\n    }\n}\n\n\/\/ Main function\nint main() {\n    int V, E;\n\n    printf("Enter number of vertices: ");\n    scanf("%d", &V);\n    printf("Enter number of edges: ");\n    scanf("%d", &E);\n\n    struct Edge edges[E];\n\n    printf("Enter edges (src dest weight): \\n");\n    for (int i = 0; i < E; i++) {\n        scanf("%d %d %d", &edges[i].src, &edges[i].dest, &edges[i].weight);\n    }\n\n    kruskal(edges, V, E);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
    Explanation of Kruskal’s Code<\/h3>\n\n\n\n
      \n
    1. Edge Structure<\/strong>: Each edge has a source, destination, and weight.<\/li>\n\n\n\n
    2. Union-Find<\/strong>: We use a Subset<\/code> structure to manage disjoint sets. The find<\/code> function retrieves the set of an element, while the unionSubsets<\/code> function merges two sets.<\/li>\n\n\n\n
    3. Sorting<\/strong>: We sort the edges by weight using qsort<\/code>.<\/li>\n\n\n\n
    4. Building the MST<\/strong>: We iterate through the sorted edges and add them to the MST if they connect disjoint sets.<\/li>\n\n\n\n
    5. Output<\/strong>: Finally, we print the edges included in the MST.<\/li>\n<\/ol>\n\n\n\n
      Sample Input and Output for Kruskal\u2019s Algorithm<\/h3>\n\n\n\n
      Input:<\/strong><\/p>\n\n\n\n
      mathematicaCopy codeEnter number of vertices: 4\nEnter number of edges: 5\nEnter edges (src dest weight):\n0 1 10\n0 2 6\n0 3 5\n1 3 15\n2 3 4\n<\/code><\/pre>\n\n\n\n
      Output:<\/strong><\/p>\n\n\n\n
      mathematicaCopy codeEdges in the Minimum Spanning Tree (Kruskal's Algorithm):\n2 -- 3 == 4\n0 -- 3 == 5\n0 -- 1 == 10\n<\/code><\/pre>\n\n\n\n
      \n