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. Implementationn");
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

Related Post

Leave a Reply

Your email address will not be published. Required fields are marked *