Prims Algorithm:
Step 1: Start
Step 2: Read a weighted Graph G(V, E)
Step 3: Let n be the number of vertices in the graph G
Step 4: Choose the starting vertex say V1 and add it to visited array
Step 5: Find the lowest cost edge coming out of Vertices in visited array
Step 6: if a cycle is formed if this lowest cost edge is drawn then
Take the next lowest cost edge
Step 7: else
Draw the edge
Add the vertex to visited array
Step 8: Go to step 3 until n-1 edges are drawn
Step 9: STOP
================================
Program:
#include<stdio.h>
int prims(int [][],int);
main()
{
int n,cost[10][10];
int mincost=0;
printf("enter number of vertices\n");
scanf("%d",&n);
printf("enter cost of each edge\n");
for(i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
printf("enter %d%d edge cost\n",i,j);
scanf("%d",&cost[i][j]);
}
}
mincost=prims(cost,n);
printf("the prim cost edge of given spanning tree is %d",mincost);
}
int prims(int cost [][],int n)
{
int mcost=0,mincostedge,t[20][20];
mincostedge=cost[1][1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(cost[i][j]<=mincostedge)
{
mincostedge=cost[i][j];
k=i;
l=j;
}
}
}
for(i=1;i<=n;i++)
{
if(cost[k][i]<cost[l][i])
near[i]=k;
else
near[i]=l;
}
near[k]=0;
near[l]=0;
mincost=mincost+cost[k][l];
t[1,1]=k;
t[1,2]=l;
for(int i=2;i<=n-1;i++)
{
for(b=1;b<=n;b++)
{
if(near[b]!=0)
{
min=cost[b][near[b]];
t[i][1]=b;
t[i][2]=near[j];
mincost=mincost+cost[j][near[j]];
near[j]=0;
for(k=1;k<n;k++)
{
if(near[k]!=0&&cost[k][near[k]]>cost[j][k])
{
near[k]=j;
}
}
return mincost;
}
Step 1: Start
Step 2: Read a weighted Graph G(V, E)
Step 3: Let n be the number of vertices in the graph G
Step 4: Choose the starting vertex say V1 and add it to visited array
Step 5: Find the lowest cost edge coming out of Vertices in visited array
Step 6: if a cycle is formed if this lowest cost edge is drawn then
Take the next lowest cost edge
Step 7: else
Draw the edge
Add the vertex to visited array
Step 8: Go to step 3 until n-1 edges are drawn
Step 9: STOP
================================
Program:
#include<stdio.h>
int prims(int [][],int);
main()
{
int n,cost[10][10];
int mincost=0;
printf("enter number of vertices\n");
scanf("%d",&n);
printf("enter cost of each edge\n");
for(i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
printf("enter %d%d edge cost\n",i,j);
scanf("%d",&cost[i][j]);
}
}
mincost=prims(cost,n);
printf("the prim cost edge of given spanning tree is %d",mincost);
}
int prims(int cost [][],int n)
{
int mcost=0,mincostedge,t[20][20];
mincostedge=cost[1][1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(cost[i][j]<=mincostedge)
{
mincostedge=cost[i][j];
k=i;
l=j;
}
}
}
for(i=1;i<=n;i++)
{
if(cost[k][i]<cost[l][i])
near[i]=k;
else
near[i]=l;
}
near[k]=0;
near[l]=0;
mincost=mincost+cost[k][l];
t[1,1]=k;
t[1,2]=l;
for(int i=2;i<=n-1;i++)
{
for(b=1;b<=n;b++)
{
if(near[b]!=0)
{
min=cost[b][near[b]];
t[i][1]=b;
t[i][2]=near[j];
mincost=mincost+cost[j][near[j]];
near[j]=0;
for(k=1;k<n;k++)
{
if(near[k]!=0&&cost[k][near[k]]>cost[j][k])
{
near[k]=j;
}
}
return mincost;
}
No comments:
Post a Comment