Thursday, 1 May 2014

Prim Algorithm C Program

/*Prim Algorithm C Program*/
#include<stdio.h>
#include<conio.h>
#define size 20
#define INFINITY 32767
void prim(int G[][size],int nodes)
{
 int tree[size],i,j,k;
 int min_dist,v1,v2,total=0;
 for(i=0;i<nodes;i++)
 {
  tree[i]=0;
 }
  printf("\n\n The minimal spaning tree is:\n");
  tree[0]=1;
  for(k=1;k<=nodes-1;k++)
  {
   min_dist=INFINITY;
   for(i=0;i<=nodes-1;i++)
   {
    for(j=0;j<=nodes-1;j++)
    {
     if(G[i][j]&&((tree[i]&&!tree[j])||(!tree[i]&&tree[j])))
     {
      if(G[i][j]<min_dist)
      {
       min_dist=G[i][j];
       v1=i;
       v2=j;
      }
     }
    }
   }
   printf("\nEdge(%d,%d) and weight=%d",v1,v2,min_dist);
   tree[v1]=tree[v2]=1;
   total=total+min_dist;
  }
  printf("\n\n\tTotal path length is=%d",total);
}
void main()
{
 int G[size][size] ,nodes;
 int v1,v2,length,i,j,n;
 clrscr();
 printf("\n\tPrim's Algorithm\n");
 printf("\nEnter the no. of nodes in Graph");
 scanf("%d",&nodes);
 printf("\nEnter the no. of edges in Graph");
 scanf("%d",&n);
 for(i=0;i<nodes;i++)
  for(j=0;j<nodes;j++)
   G[i][j]=0;
   printf("Enter Edge and weight");
   for(i=0;i<n;i++)
   {
    printf("\nEnter edge by v1&v2:");
    printf("[read the graph from starting node[0]]");
    scanf("%d%d",&v1,&v2);
    printf("Enter the corresponding weight");
    scanf("%d",&length);
    G[v1][v2]=G[v2][v1]=length;
   }
 getch();
 printf("\n\t");
 clrscr();
 prim(G,nodes);
 getch();
}


No comments:

Post a Comment