Program to find Minimum Spanning Tree MST of a graph using Kruskal’s Algorithm in C

Program

#include <stdio.h>
#include <conio.h>
int ne = 1, min_cost = 0;
void main()
{
    int n, i, j, min, a, u, b, v, cost[20][20], parent[20];
    printf("****************************************************************");
    printf("\n****************************************************************");
    printf("\n**      WAP to find Minimum Spanning Tree MST of a graph      **");
    printf("\n**              using Kruskal's Algorithm in C                **");
    printf("\n**                   Created by Sheetal Garg                  **");
    printf("\n**                     Assistant Professor                    **");
    printf("\n**                     Phone No:9467863365                    **");
    printf("\n****************************************************************");
    printf("\n****************************************************************");
    printf("\nEnter the no. of vertices:");
    scanf("%d", &n);
    printf("\nEnter the cost matrix:\n");
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
            scanf("%d", &cost[i][j]);
    }
    for (i = 1; i <= n; i++)
        parent[i] = 0;
    printf("\nThe edges of spanning tree are\n");
    while (ne < n)
    {
        min = 999;
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                if (cost[i][j] < min)
                {
                    min = cost[i][j];
                    a = u = i;
                    b = v = j;
                }
            }
        }
        while (parent[u])
            u = parent[u];
        while (parent[v])
            v = parent[v];
        if (u != v)
        {
            printf("Edge %d\t(%d->%d)=%d\n", ne++, a, b, min);
            min_cost = min_cost + min;
            parent[v] = u;
        }
        cost[a][b] = cost[a][b] = 999;
    }
    printf("\nMinimum cost=%d\n", min_cost);
    getch();
}

Output

****************************************************************
****************************************************************
**      WAP to find Minimum Spanning Tree MST of a graph      **
**              using Kruskal's Algorithm in C                **
**                   Created by Sheetal Garg                  **
**                     Assistant Professor                    **
**                     Phone No:9467863365                    **
****************************************************************
****************************************************************
Enter the no. of vertices:
4

Enter the cost matrix:
3 4 5 2
4 7 8 3
2 3 4 1
6 7 5 3

The edges of spanning tree are
Edge 1  (3->4)=1
Edge 2  (1->4)=2
Edge 3  (2->4)=3

Minimum cost=6