Kruskal's Algorithm

Kruskal's Algorithm

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
enum logical {TRUE=1,FALSE=0} ;

struct edge
{
                int from,to ;
                float cost ;
                int tree_no ;
};
                int nv,ne,k=0 ;
                struct edge e[20] ;
void greedy_kruskal();
logical feasible(int pos);
void main()
{
                clrscr();
                int i ;
                float temp;
                scanf("%f",&temp);
                printf("\nNo. of vertices = ");
                scanf("%d",&nv);
                printf("\nNo. of edges = ");
                scanf("%d",&ne);
                printf("\nEnter end-vertices and cost for each edge ");
                for(i=1;i<=ne;i++)
                {
                                printf("\nEnter for edge: %d",i);
                                printf("\nEnter from vertice: ");
                                scanf("%d",&e[i].from);
                                printf("\nEnter to vertice: ");
                                scanf("%d",&e[i].to);
                                printf("\nEnter the cost: ");
                                scanf("%f",&e[i].cost);
                                e[i].tree_no=0 ;
                }

                greedy_kruskal();

                                float mincost=0 ;

                cout << "Edge      Cost" << endl ;
                cout << "-----  -------" << endl ;
                for(i=1;i<=ne;i++)
                {
                                if(e[i].tree_no>0)
                                {
                                                printf("\n(%d - %d) - %.2f",e[i].from,e[i].to,e[i].cost);
                                                mincost += e[i].cost ;
                                }
                }
                printf("\n            -------");
                printf("\n Total %.2f",mincost);
getch();
}
void greedy_kruskal()
{
                int count=1,j,pos ;
                float min ;
                while(count<=nv-1)
                {
                                min=9999 ; pos=0 ;
                                for(j=1;j<=ne;j++)
                                {
                                                if(e[j].tree_no!=0)
                                                                continue ;
                                                if(e[j].cost<min)
                                                {
                                                                min=e[j].cost ;
                                                                pos=j ;
                                                }
                                }
                                if(feasible(pos))
                                {
                                                count++ ;
                                }
                }
}

logical feasible(int pos)
{
                int i,tr1=0,tr2=0 ;
                for(i=1;i<=ne;i++)
                {
                                if(e[i].tree_no>0)
                                {
                                                if(e[pos].from==e[i].from || e[pos].from==e[i].to)
                                                                tr1=e[i].tree_no ;
                                                if(e[pos].to==e[i].from || e[pos].to==e[i].to)
                                                                tr2=e[i].tree_no ;
                                }
                }
                if(tr1==0 && tr2==0)
                {
                                k++ ;
                                e[pos].tree_no=k;
                                return TRUE ;
                }
                if(tr1==0 && tr2!=0)
                {
                                e[pos].tree_no=tr2 ;
                                return TRUE ;
                }
                if(tr1!=0 && tr2==0)
                {
                                e[pos].tree_no=tr1 ;
                                return TRUE ;
                }
                if(tr1==tr2)
                {
                                e[pos].tree_no=-1 ;
                                return FALSE ;
                }
                e[pos].tree_no=tr1 ;
                for(i=1;i<=ne;i++)
                {
                                if(e[i].tree_no==tr2)
                                {
                                                e[i].tree_no=tr1 ;
                                }
                }
                return TRUE ;
}