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

DWDM 2024 question paper with solution

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