Prim's algorithm in C.

01 #include<stdio.h>
02 
03 #define INFINITY 999
04 
05 int main()
06 {
07     int a,b,u,v,n,i,j,ne=1;
08     int visited[10]= {0},cost[10][10];
09     int min,mincost=0;
10 
11     printf("Prims Algo. Implementation\n");
12     printf("\nEnter the number of nodes : ");
13     scanf("%d",&n);
14     printf("\nEnter Costs for NODES : \n");
15 
16     for(i=1; i<=n; i++)
17     {
18         for(j=1; j<=n; j++)
19         {
20             printf("Cost -> Node [%d] to Node[%d] : ",i,j);
21             scanf("%d",&cost[i][j]);
22             if(cost[i][j]==0)
23                 cost[i][j]=INFINITY;
24         }
25         printf("\n");
26     }
27     visited[1]=1;
28     printf("\n");
29 
30     while(ne<n)
31     {
32         for(i=1,min=INFINITY; i<=n; i++)
33             for(j=1; j<=n; j++)
34                 if(cost[i][j]<min)
35                     if(visited[i]!=0)
36                     {
37                         min=cost[i][j];
38                         a=u=i;
39                         b=v=j;
40                     }
41 
42         if(visited[u]==0 || visited[v]==0)
43         {
44             printf("\n Edge %d:(%d %d) cost : %d",ne++,a,b,min);
45             mincost+=min;
46             visited[b]=1;
47         }
48         cost[a][b]=cost[b][a]=INFINITY;
49     }
50     printf("\n Minimun Cost of Spanning Tree = %d",mincost);
51     return 0;
52 }

 OUTPUT :
 
 Prims Algo. Implementation
 
 Enter the number of nodes : 4
 
 Enter Costs for NODES :
 Cost -> Node [1] to Node[1] : 0
 Cost -> Node [1] to Node[2] : 10
 Cost -> Node [1] to Node[3] : 9
 Cost -> Node [1] to Node[4] : 18
 
 Cost -> Node [2] to Node[1] : 10
 Cost -> Node [2] to Node[2] : 0
 Cost -> Node [2] to Node[3] : 5
 Cost -> Node [2] to Node[4] : 0
 
 Cost -> Node [3] to Node[1] : 9
 Cost -> Node [3] to Node[2] : 5
 Cost -> Node [3] to Node[3] : 0
 Cost -> Node [3] to Node[4] : 7
 
 Cost -> Node [4] to Node[1] : 18
 Cost -> Node [4] to Node[2] : 0
 Cost -> Node [4] to Node[3] : 7
 Cost -> Node [4] to Node[4] : 0
 
 
 
  Edge 1:(1 3) cost : 9
  Edge 2:(3 2) cost : 5
  Edge 3:(3 4) cost : 7
  Minimun Cost of Spanning Tree = 21