DAA-Prims algorithm with program(BCA-IV sem)KSWU

  

Experiment No: 9 Aim: Program to compute minimum spanning tree using Prim’s Algorithm.

 

ALGORITHM :

Algorithm:

Prim(E,cost,n,t)

//E is the set of edges in G.cost [1:n,1:n] is the cost

//adjacency matrix of an n vertex graph such that cost[i,j] is

//either a positive real number or infinity if no edge of (i,j) exists

//a minimum spanning tree is computed and stored as a set of

//edges in the array t[1:n-1,1:2] . (t[i,1],t[i,2] is an edge in the minimum cost spanning

//tree .The final cost is returned.

{

 Let (k,l) be an edge of minimum cost in Ei

mincost :=cost[k,l];

t[1,1]:=k;t[1,2]:=l;

for i:=1 to n do //initialize near

if(cost[i,l]<cost[i,k]) then near[i] :=l;

else

near[i]:=k;

near[k]:=near [l]:=0;

for i:=2 to n-1 do

{

// Find n-2 additional edges for t

Let j be an index such that near[j]!=0and

Cost[j,near[j]] is minimum

 t[i,1]:=j;t[i,2]:=near[j];

 mincost :=mincost+cost[j,near[j]];

near[j]:=0;

for k:=1 to n do //Update near[].

 if((near[k]!=0) and (cost[k,near[k]]>cost[k,j]))

 then near[k]:=j;

}

return mincost;

}

SOURCE CODE : 

#include<stdio.h>
#include<conio.h>
#include<time.h>
int n,cost[10][10],temp,nears[10];
void readv();
void primsalg();
void readv()
{
int i,j;
clock_t start,end;
double cpu_time_used;
start=clock();
printf("\nEnter the No of nodes or vertices:");
scanf("%d",&n);
printf("\nEnter the cost Adjacency matrix of the given graph:");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if((cost[i][j]==0)&&(i!=j))
{
cost[i][j]=999;
}
}
}
end=clock();
cpu_time_used=((double)(end-start))/CLOCKS_PER_SEC;
printf("The time taken for execution is %f seconds",cpu_time_used);
}
void primsalg()
{
int k,l,min,a,t[10][10],u,i,j,mincost=0;
min=999;
for(i=1;i<=n;i++)
{
for(u=1;u<=n;u++)
{
if(i!=u)
{
if(cost[i][u]<min)
{
min=cost[i][u];
k=i;
l=u;
}
}
}
}
t[1][1]=k;
t[1][2]=l;
printf("\n The Minimum cost Spanning tree is...");
printf("\n(%d,%d)-->%d",k,l,min);
for(i=1;i<=n;i++)
{
if(i!=k)
{ if(cost[i][l]<cost[i][k])
{
nears[i]=l;
}
else
{
nears[i]=k;
}
}
}
nears[k]=nears[l]=0;
mincost=min;
for(i=2;i<=n-1;i++)
{
j=findextindex(cost,nears);
t[i][1]=j;
t[i][2]=nears[j];
printf("\n(%d,%d)-->%d",t[i][1],t[i][2],cost[j][nears[j]]);
mincost=mincost+cost[j][nears[j]];
nears[j]=0;
for(k=1;k<=n;k++)
{
if(nears[k]!=0&&cost[k][nears[k]]>cost[k][j])
{
nears[k]=j;
}
}
}
printf("\n The Required Mincost of the spanning tree is:%d",mincost);
}
int findextindex(int cost[10][10],int nears[10])
{
int min=999,a,k,p;
for(a=1;a<=n;a++)
{
p=nears[a];
if(p!=0)
{
if(cost[a][p]<min)
{
min=cost[a][p];
k=a;
}
}
}
return k;
}
void main()
{
clrscr();
readv();
primsalg();
getch();
}

OUTPUT 1 :  WITH TIME COMPLEXITY 

OUTPUT : WITHOUT TIME COMPLEXITY

OUTPUT 2 :