14 April, 2012

prims

#include<stdio.h>
int **cost,n,**t,v,*s;
int find(int *);
int prim(int *);
int main()
{
        int i,j,temp;
        printf("Enter no.of vertices in graph\n");
        scanf("%d",&n);
        cost=(int **)malloc(n*sizeof(int *));
        for(i=0;i<n;i++)
        cost[i]=(int *)malloc(n*sizeof(int));
        printf("Enter distances\n");
        for(i=0;i<n;i++)
        {
                for(j=0;j<n;j++)
                {
                        if(i==j)
                        cost[i][j]=1000;
                        else
                        cost[i][j]=10000;
                }
        }
        for(i=0;i<n;i++)
        {
                for(j=0;j<n;j++)
                {
                        if(cost[i][j]==10000)
                        {
                                scanf("%d",&temp);
                                cost[j][i]=temp;
                                cost[i][j]=temp;
                        }
                }
        }
        int *near=(int *)malloc(n*sizeof(int *));
        t=(int **)malloc(n*sizeof(int *));
        for(i=0;i<n;i++)
        t[i]=(int *)malloc(2*sizeof(int));
        printf("\nMinimum cost=%d\n",prim(near));
        for(i=0;i<n;i++)
        printf("%d      %d\n",t[i][0]+1,t[i][1]+1);
}
int find(int *near)
{
        int i,min=10000,j;
        for(i=0;i<n;i++)
        {
                if(near[i]!=-1&&(cost[i][near[i]]<min))
                {
                        j=i;
                        min=cost[i][near[i]];
                }
        }
        return j;
}
int prim(int *near)
{
        int mincost=0,j,k,i;
        for(i=1;i<n;i++)
        near[i]=0;
        near[0]=-1;
        for(i=1;i<n;i++)
        {
                j=find(near);
                t[i][0]=j;
                t[i][1]=near[j];
                mincost+=cost[j][near[j]];
                near[j]=-1;
                for(k=1;k<n;k++)
                {
                        if(near[k]!=-1&&(cost[k][near[k]]>cost[k][j]))
                        near[k]=j;
                }
        }
        return mincost;
}

No comments:

Post a Comment