## Pages

### 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 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();
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
{
}
}
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("\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.predecessor=0;
state.dist = 0;
state.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 )
{
{
state[i].predecessor = current;
}
}
}

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