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;

          struct edge *link;

}*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 )

          {

                   tmp->link = front;

                   front = tmp;

          }

          else

          {

                   q = front;

                   while( q->link != NULL && q->link->weight <= tmp->weight )

                             q=q->link;

                   tmp->link = q->link;

                   q->link = tmp;

                   if(q->link == NULL)

                             tmp->link = NULL;

          }

}

struct edge *del_pque()

{

          struct edge *tmp;

          tmp = front;

printf("\nEdge processed is %d->%d  %d\n",tmp->u,tmp->v,tmp->weight);

          front = front->link;

          return tmp;

}


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.