Find minimum spanning tree using kruskal algorith in c Language

 #include <stdio.h>


int find(int i, int parent[]) {

    while (parent[i] != i)

        i = parent[i];

    return i;

}


void union_set(int i, int j, int parent[]) {

    int a = find(i, parent);

    int b = find(j, parent);

    parent[b] = a;

}


void kruskal(int n, int edges[20][3], int e) {

    int parent[20];

    int i, j, u, v, cost = 0, count = 0;


    // Step 1: MakeSet(v) → initialize parent[i] = i

    for (i = 1; i <= n; i++)

        parent[i] = i;


    // Step 2: Sort edges in ascending order of weight

    for (i = 0; i < e - 1; i++) {

        for (j = i + 1; j < e; j++) {

            if (edges[i][2] > edges[j][2]) {

                int temp0 = edges[i][0];

                int temp1 = edges[i][1];

                int temp2 = edges[i][2];

                edges[i][0] = edges[j][0];

                edges[i][1] = edges[j][1];

                edges[i][2] = edges[j][2];

                edges[j][0] = temp0;

                edges[j][1] = temp1;

                edges[j][2] = temp2;

            }

        }

    }


    printf("\nEdges in the Minimum Spanning Tree:\n");


    // Step 3: For each edge (u,v) in ascending order

    for (i = 0; i < e; i++) {

        u = edges[i][0];

        v = edges[i][1];


        // Step 4: If Find(u) ≠ Find(v)

        if (find(u, parent) != find(v, parent)) {

            printf("(%d, %d)  cost = %d\n", u, v, edges[i][2]);

            cost += edges[i][2];

            count++;

            union_set(u, v, parent);

        }


        if (count == n - 1)

            break;

    }


    printf("\nTotal cost of Minimum Spanning Tree = %d\n", cost);

}


int main() {

    int n, e, i;

    int edges[20][3];


    printf("Enter number of vertices: ");

    scanf("%d", &n);


    printf("Enter number of edges: ");

    scanf("%d", &e);


    printf("Enter edges (u v w):\n");

    for (i = 0; i < e; i++) {

        scanf("%d%d%d", &edges[i][0], &edges[i][1], &edges[i][2]);

    }


    kruskal(n, edges, e);

    return 0;

}


Comments

Popular posts from this blog

B.tech 5th Sem Machin learning lab practical

BCA 3rd year Web Technology(code 304) Web Site development using ASP.NET AND C#

DWDM 2024 question paper with solution