Trend Posts
Author
View LUQMAN's profile
Showing posts with label Prim's Algorithm. Show all posts
Showing posts with label Prim's Algorithm. Show all posts
Monday, July 21, 2014
/*Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.*/
#include<stdio.h>
int i,j,min,nearv[100],cost[100][100],t[100][100],s,n,u,mincost=0,k;
void prims()
{
for(i=2;i<=n;i++)
nearv[i]=1;
nearv[1]=0;
for(i=1;i<n;i++)
{
min=999;
for(j=1;j<=n;j++)
{
if(nearv[j]!=0 && cost[j][nearv[j]]<min)
{
min=cost[j][nearv[j]];
u=j;
}
}
t[i][1]=u;
t[i][2]=nearv[u];
mincost+=min;nearv[u]=0;
for(k=1;k<=n;k++)
{
if(nearv[k]!=0 && cost[k][nearv[k]]>cost[k][u])
nearv[k]=u;
}
printf("%d)edge(%d,%d),cost=%d\n",i,t[i][1],t[i][2],min);
}
}
void main()
{
printf("\nEnter the number of nodes\n");
scanf("%d",&n);
printf("\nEnter the weight of each nodes\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("\nEntered weights are:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
prims();
}
Subscribe to:
Posts (Atom)