## Pages

### Kruskals Algorithm C program Data Structure

This program is for Kruskals Alogrithm in C programing. This is a part of Mumbai University MCA Colleges Data Structure C program MCA Sem 2

#include<stdio.h>
#include<conio.h>
#define MAX 20

struct edge
{
int u;
int v;
int weight;
}*front = NULL;

int father[MAX];
struct edge tree[MAX];
int n;
int wt_tree=0;
int count=0;

void make_tree();
void insert_tree(int i,int j,int wt);
void insert_pque(int i,int j,int wt);
struct edge *del_pque();

main()
{
int i;
clrscr();
printf("******************** MINIMUM SPANNING TREE FROM KRUSKAL'S ALGORITHM **************\n");
create_graph();
make_tree();
printf("\nEdges to be included in spanning tree are : \n");
for(i=1;i<=count;i++)
{
printf("%d->",tree[i].u);
printf("%d\n",tree[i].v);
}
printf("\nWeight of this minimum spanning tree is : %d\n", wt_tree);
getch();
}

create_graph()
{
int i,wt,max_edges,origin,destin;

printf("\nEnter number of nodes : ");
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
insert_pque(origin,destin,wt);
}
if(i<n-1)
{
printf("\nSpanning tree is not possible\n");
exit(1);
}
}

void make_tree()
{
struct edge *tmp;
int node1,node2,root_n1,root_n2;

while( count < n-1)
{
tmp=del_pque();
node1=tmp->u;
node2=tmp->v;

printf("n1=%d  ",node1);
printf("n2=%d  ",node2);

while( node1 > 0)
{
root_n1=node1;
node1=father[node1];
}
while( node2 >0 )
{
root_n2=node2;
node2=father[node2];
}
printf("rootn1=%d  ",root_n1);
printf("rootn2=%d\n",root_n2);

if(root_n1!=root_n2)
{
insert_tree(tmp->u,tmp->v,tmp->weight);
wt_tree=wt_tree+tmp->weight;
father[root_n2]=root_n1;
}
}
}

void insert_tree(int i,int j,int wt)
{
printf("\nThis edge inserted in the spanning tree\n");
count++;
tree[count].u=i;
tree[count].v=j;
tree[count].weight=wt;
}

void insert_pque(int i,int j,int wt)
{
struct edge *tmp,*q;

tmp = (struct edge *)malloc(sizeof(struct edge));
tmp->u=i;
tmp->v=j;
tmp->weight = wt;

if( front == NULL || tmp->weight < front->weight )
{
front = tmp;
}
else
{
q = front;
}
}

struct edge *del_pque()
{
struct edge *tmp;
tmp = front;
printf("\nEdge processed is %d->%d  %d\n",tmp->u,tmp->v,tmp->weight);