problem on MST

general
, ,
1

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…

2

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**=inf

cost[C]=inf

Adj vertices B and C.

A-B<cost**//true

cost**=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**//true{This shouldn't happened had you kept the seen vertices in account}

cost**=0.5

MST value=cost[A]+cost**+cost[C]=0+.5+.5=1(Wrong.)Correct answer is 1.5

1 Like
3

#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;

}