# problem on MST

recently i was trying to implement the prim’s algorithm. i tried to modify the algo a bit according to my understanding but am getting wrong answer on that.
can someone tell me a test case on where my algo is going wrong …

``````n//total vertices

g[][]//the adjacency matrix for the graph

cost[]//stores the edge value

for(i=0;i<n;i++){

for(j=0;j<n;j++){
if(g[i][j]<c[j])
c[j]=g[i][j];}}
``````

now to find the value of the MST am summing up the entire c[] array and that is the final answer…
here is my implementation…

The problem is that you’re not keeping account of the seen nodes in the graph.Thus, the nodes which you’ve already discovered also get updated which shouldn’t be the case as Prim’s MST takes the optimal decision from the fringe vertices.

An example where your code fails:
Edges:

A-B=1

B-C=0.5

A-C=3

Start from A.

cost[A]=0

cost[B]=inf

cost[C]=inf

``````A-B<cost[B]//true
``````

cost[B]=1

``````A-C<cost[C]//true
``````

cost[C]=3

next iteration-B

``````B-A<cost[A]//false

B-C<cost[C]//true
``````

cost[C]=0.5

next iteration-C

``````C-A<cost[A]//false

C-B<cost[B]//true{This shouldn't happened had you kept the seen vertices in account}
``````

cost[B]=0.5

1 Like

#include<stdio.h>
int a[100][100],temp[20]={0},t=0,n;
int min(int i)
{
int k,j,min=32767,mj,mi;
temp[++t]=i;
for(k=1;k<=t;k++)
{
for(j=1;j<=n;j++)
{
if(min>a[temp[k]][j])
{
min=a[temp[k]][j];
mj=j;
mi=temp[k];
}
}
}
printf("\n%d to %d",mi,mj);
return mj;
}
int main()
{
int i,j,c=0,b;
printf(“Enter the no. of vertices=”);
scanf("%d",&n);
printf("\nEnter the cost matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
i=1;
while(c<(n-1))
{
b=min(i);
a[i][b]=32767;
a[b][i]=32767;
i=b;
c++;

``````}
return 0;
``````

}