Prim's Algorithm

1:  #include<stdio.h>  
2:  #include<conio.h>  
3:  void main()  
4:  {  
5:  int n,i,j,c[20][20],k,l,t[2][2],min=9999,mincost,n1[10]={0},min1=9999,j1;  
6:  clrscr();  
7:  printf("\n\tMINIMUM SPANNING TREE");  
8:  printf("\n\tENTER THE NO OF NODES");  
9:  scanf("%d",&n);  
10:  printf("\n\tENTER THE COST MATRIX");  
11:  printf("\n\tENTER 9999 for INFINITY");  
12:  for(i=1;i<=n;i++)  
13:  {  
14:       for(j=1;j<=n;j++)  
15:       {  
16:            if(i==j)  
17:            {  
18:            c[i][j]=0;  
19:            }  
20:       }  
21:  }  
22:  for(i=1;i<=n;i++)  
23:  {  
24:       for(j=i+1;j<=n;j++)  
25:       {  
26:       printf(" COST [%d][%d]: ",i,j);  
27:       scanf("%d",&c[i][j]);  
28:       }  
29:  }  
30:  for(i=2;i<=n;i++)  
31:  {  
32:       for(j=1;j<i;j++)  
33:       {  
34:       c[i][j]=c[j][i];  
35:       }  
36:  }  
37:  for(i=1;i<=n;i++)  
38:  {  
39:       for(j=i+1;j<=n;j++)  
40:       {  
41:            if(min>c[i][j])  
42:            {  
43:            min=c[i][j];  
44:            k=i;  
45:            l=j;  
46:            }  
47:       }  
48:  }  
49:  mincost=min;  
50:  min=9999;  
51:  t[1][1]=k;  
52:  t[1][2]=l;  
53:  for(i=1;i<=n;i++)  
54:  {  
55:       if(c[i][l]<c[i][k])  
56:       {  
57:       n1[i]=l;  
58:       }  
59:       else  
60:       n1[i]=k;  
61:  }  
62:  n1[k]=0;  
63:  n1[l]=0;  
64:  for(i=2;i<=n-1;i++)  
65:  {  
66:       for(j=1;j<=n;j++)  
67:       {  
68:            if(n1[j]!=0)  
69:            {  
70:                 if(min1>c[j][n1[j]])  
71:                 {  
72:                 min1=c[j][n1[j]];  
73:                 j1=j;  
74:                 }  
75:            }  
76:       }  
77:       t[i][1]=j1;  
78:       t[i][2]=n1[j1];  
79:       printf("%d\n%d",t[i][1],t[i][2]);  
80:       mincost=mincost+c[j1][n1[j1]];  
81:       min1=9999;  
82:       n1[j1]=0;  
83:       for(k=1;k<=n;k++)  
84:       {  
85:            if(n1[k]!=0)  
86:            {  
87:                 if((c[k][n1[k]])>(c[k][j1]))  
88:                 {  
89:                 n1[k]=j1;  
90:                 }  
91:            }  
92:       }  
93:  }  
94:  for(i=1;i<=n;i++)  
95:  {  
96:  for(j=1;j<=n;j++)  
97:  {  
98:  printf("%d",t[i][j]);  
99:  }  
100:  printf("\n");  
101:  }  
102:  printf("%d",mincost);  
103:  getch();  
104:  }