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.

No comments:

Post a comment