/* 1(b). W.A.P. to obtain the minimum cost spanning tree of a given undirected connected graph using Prim's algorithm. */

#include<stdio.h>
#include<conio.h>
void main()
{    
    int i,j,n,min,u,v,cost[10][10],visible[10],wt=0,count;
    clrscr();
    printf("Enter no. of vertices : ");
    scanf("%d",&n);
    printf("\nEnter the cost adjacency matrix [99 to indicate no edge] :\n");
    for (i = 0; i < n; i++)
    {
        visible[i]=0;
        for (j = 0; j < n; j++)
        {
            scanf("%d",&cost[i][j]);
            if (cost[i][j] == 0)
                cost[i][j] = 99; // To indicate no edge
        }
    }
    visible[0] = count = 1; // Start from vertex 1
    printf("\nEdges of the minimum spanning tree is :");
    while (count < n)
    {
        min=99;
        // To compute mininum weight of an edge from selected vertices only
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                {
                    if (visible[i] == 0)
                        continue;
                    if (cost[i][j] < min)
                        {
                            min = cost[i][j];
                            u = i; // Minimum weight's ROW index value
                            v = j; // Minimum weight's COLUMN index value
                        }
                }
        cost[u][v] = cost[v][u] = 99; // Make undirected graph
        if (!visible[u] || !visible[v]) // Check whether vertex selected or not
            {
                printf("\n< %d , %d >",u+1,v+1);
                wt = wt + min; // Add minimum weight
                visible[u] = visible[v] = 1; // Vertices selected
            }
            count++;
    }
    printf("\nThe solution to minimum weight spanning tree is %d",wt);
}
/* OUTPUT
Enter no. of vertices : 3
Enter the cost adjacency matrix :
0 10 1
10 0 6
1 6 0
Edges of the minimum spanning tree is :
< 1 , 3 >
< 3 , 2 >
The solution to minimum weight spanning tree is 7
*/