C Program to implement prims algorithm using greedy method

   

C Program to implement prims algorithm using greedy method

#include<stdio.h>
#include<conio.h>

int n, cost[10][10];

void prim()
{
 int i,j,k,l,x,nr[10],temp,min_cost=0,tree[10][3];
 /* For first smallest edge */
 temp=cost[0][0];
 for(i=0;i< n;i++)
 {
     for(j=0;j< n;j++)
     {
        if(temp>cost[i][j])
        {
        temp=cost[i][j];
        k=i;
        l=j;
        }
     }
 }
 /* Now we have fist smallest edge in graph */
 tree[0][0]=k;
 tree[0][1]=l;
 tree[0][2]=temp;
 min_cost=temp;

 /* Now we have to find min dis of each 
vertex from either k or l
by initialising nr[] array 
*/

 for(i=0;i< n;i++)
    {
    if(cost[i][k]< cost[i][l])
        nr[i]=k;
    else
        nr[i]=l;
    }
 /* To indicate visited vertex initialise nr[] for them to 100 */
 nr[k]=100;
 nr[l]=100;
 /* Now find out remaining n-2 edges */
 temp=99;
 for(i=1;i< n-1;i++)
    {
    for(j=0;j< n;j++)
       {
       if(nr[j]!=100 && cost[j][nr[j]] < temp)
           {
           temp=cost[j][nr[j]];
           x=j;
           }
       }
 /* Now i have got next vertex */
 tree[i][0]=x;
 tree[i][1]=nr[x];
 tree[i][2]=cost[x][nr[x]];
 min_cost=min_cost+cost[x][nr[x]];
 nr[x]=100;

 /* Now find if x is nearest to any vertex 
than its previous near value */

    for(j=0;j< n;j++)
    {
    if(nr[j]!=100 && cost[j][nr[j]] > cost[j][x])
         nr[j]=x;
    }
    temp=99;
 }
 /* Now i have the answer, just going to print it */
 printf("n The min spanning tree is:- ");
 for(i=0;i< n-1;i++)
    {
    for(j=0;j< 3;j++)
           printf("%d", tree[i][j]);
    printf("n");
    }

 printf("n Min cost:- %d", min_cost);
}

//////////////////////////////////////////////
void main()
{
 int i,j;
 clrscr();

 printf("n Enter the no. of vertices:- ");
 scanf("%d", &n);

 printf ("n Enter the costs of edges in matrix form:- ");
 for(i=0;i< n;i++)
     for(j=0;j< n;j++)
          scanf("%d",&cost[i][j]);

 printf("n The matrix is:- ");
    for(i=0;i< n;i++)
    {
      for(j=0;j< n;j++)
           printf("%dt",cost[i][j]);
      printf("n");
    }
 prim();
 getch();
}

Output :

Enter the no. of vertices:- 3

 Enter the costs of edges in matrix form:-
99 2 3
2 99 5
3 5 99

The matrix is:-
99      2       3
2       99      5
3       5       99

The min spanning tree is:-
0  1  2
2  0  3

Min cost:- 5