Sunday 17 March 2019

C program Prims spanning tree

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

No comments:

Post a Comment