PROGRAM:
//prims algorithm
#include<stdio.h> //header file
int main()
{
int vis[10],a[10][10],cos[10]={99,99,99,99,99,99,99,99,99,99},sours[10];
int j,i,n,source;
printf("\nPRIMS ALGORITHM\n");
printf("\nEnter the total number of nodes\t:");
scanf("%d",&n); //getting total number of elements
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++) //getting adjacency from user
{
printf("\nEnter whether adjacency exists from %d to %d\t:",i,j);
scanf("%d",&a[i][j]);
}
}
for(i=1;i<=n;i++)
{
vis[i]=0; //setting zero to array (visited)
}
printf("\nEnter the source node\t:");
scanf("%d",&source);
cos[source]=0; //assigning zero to source
sours[source]=source; //assigning the same node as a source to it
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(a[i][j]!=0) //checking or obtaining the weight of the edge
{
if(vis[j]==0||vis[j]!=0)
{
vis[j]=1;
if(cos[j]>a[i][j]) //checking whether initial cost exceeds new cost
{
cos[j]=a[i][j]; //assigning new cost
sours[j]=i; //assigning the reference node
}
}
}
}
}
printf("\nNODE\tCOST\tSOURCE\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j)
{
printf("\n%d\t%d\t%d\n",i,cos[i],sours[j]); //printing the result
}
}
}
return 0;
}
OUTPUT:
PRIMS ALGORITHM
No comments:
Post a Comment