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.

No comments:

Post a comment