Prims Algorithm C Program Data Structure

This Program is for Prims Algorithm in C. This is a part of Mumbai University MCA Colleges Data Structure C program MCA Sem 2

#include<stdio.h>

#include<conio.h>

#define MAX 10

#define TEMP 0

#define PERM 1

#define FALSE 0

#define TRUE 1

#define infinity 9999

struct node

{

          int predecessor;

          int dist;

          int status;

};

struct edge

{

          int u;

          int v;

};

int adj[MAX][MAX];

int n;

main()

{

          int i,j;

          int path[MAX];

          int wt_tree,count;

          struct edge tree[MAX];

          clrscr();

printf("********* MINIMUM SPANNING TREE FROM PRIM'S ALGORITHM ********\n");

          create_graph();

          printf("\nAdjacency matrix is : \n\n");

          display();

          count = maketree(tree,&wt_tree);

          printf("\nWeight of spanning tree is : %d\n", wt_tree);

          printf("\nEdges to be included in spanning tree are : \n\n");

          for(i=1;i<=count;i++)

          {

                   printf("%d->",tree[i].u);

                   printf("%d\n",tree[i].v);

          }

          getch();

}

create_graph()

{

          int i,max_edges,origin,destin,wt;

          printf("\nEnter number of vertices : ");

          scanf("%d",&n);

          max_edges=n*(n-1)/2;

          for(i=1;i<=max_edges;i++)

          {

                   printf("\nEnter edge %d(0 0 to quit) : ",i);

                   scanf("%d %d",&origin,&destin);

                   if((origin==0) && (destin==0))

                             break;

                   printf("\nEnter weight for this edge : ");

                   scanf("%d",&wt);

                   if( origin > n || destin > n || origin<=0 || destin<=0)

                   {

                             printf("\nInvalid edge!\n");

                             i--;

                   }

                   else

                   {

                             adj[origin][destin]=wt;

                             adj[destin][origin]=wt;

                   }

          }

          if(i<n-1)

          {

                   printf("\nSpanning tree is not possible\n");

                   exit(1);

          }

}

display()

{

          int i,j;

          for(i=1;i<=n;i++)

          {

                   for(j=1;j<=n;j++)

                             printf("%3d",adj[i][j]);

                   printf("\n");

          }

}

int maketree(struct edge tree[MAX],int *weight)

{

          struct node state[MAX];

          int i,k,min,count,current,newdist;

          int m;

          int u1,v1;

          *weight=0;

          for(i=1;i<=n;i++)

          {

                   state[i].predecessor=0;

                   state[i].dist = infinity;

                   state[i].status = TEMP;

          }

          state[1].predecessor=0;

          state[1].dist = 0;

          state[1].status = PERM;

          current=1;

          count=0;

          while( all_perm(state) != TRUE )

          {

                   for(i=1;i<=n;i++)

                   {

                             if ( adj[current][i] > 0 && state[i].status == TEMP )

                             {

                                      if(  adj[current][i] < state[i].dist )

                                      {

                                                state[i].predecessor = current;

                                                state[i].dist = adj[current][i];

                                      }

                             }

                   }

                   min=infinity;

                   for(i=1;i<=n;i++)

                   {

                             if(state[i].status == TEMP && state[i].dist < min)

                             {

                                      min = state[i].dist;

                                      current=i;

                             }

                   }

                   state[current].status=PERM;

                   u1=state[current].predecessor;

                   v1=current;

                   count++;

                   tree[count].u=u1;

                   tree[count].v=v1;

                   *weight=*weight+adj[u1][v1];

          }

          return (count);

}

int all_perm(struct node state[MAX] )

{

          int i;

          for(i=1;i<=n;i++)

             if( state[i].status == TEMP )

                 return FALSE;

          return TRUE;

}

Hope this Program is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.