BCSL404 Program 1

#define INF 999
#define MAX 100
int p[MAX], c[MAX][MAX], t[MAX][2];
int find(int v)
{
    while (p[v])
        v = p[v];
    return v;
}
void union1(int i, int j)
{
    p[j] = i;
}
void kruskal(int n)
{
    int i, j, k, u, v, min, res1, res2, sum = 0;
    for (k = 1; k < n; k++)
    {
        min = INF;
        for (i = 1; i < n - 1; i++)
        {
            for (j = 1; j <= n; j++)
            {
                if (i == j) continue;
                if (c[i][j] < min)
                {
                    u = find(i);
                    v = find(j);
                    if (u != v)
                    {
                        res1 = i;
                        res2 = j;
                        min = c[i][j];
                    }
                }
            }
        }
        union1(res1, find(res2));
        t[k][1] = res1;
        t[k][2] = res2;
        sum = sum + min;
    }
    printf("\nCost of spanning tree is=%d", sum);
    printf("\nEdgesof spanning tree are:\n");
    for (i = 1; i < n; i++)
        printf("%d -> %d\n", t[i][1], t[i][2]);
}
int main()
{
    int i, j, n;
    printf("\nEnter the n value:");
    scanf("%d", & n);
    for (i = 1; i <= n; i++)
        p[i] = 0;
    printf("\nEnter the graph data:\n");
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            scanf("%d", & c[i][j]);
    kruskal(n);
    return 0;
}

Enter the n value:5

Enter the graph data:
1 3 4 6 2
1 7 6 9 3
5 2 8 99 45
1 44 66 33 6
12 4 3 2 0

Cost of spanning tree is=11
Edgesof spanning tree are:
2 -> 1
1 -> 5
3 -> 2
1 -> 4