Greedy Prim Algorithm using c/c++

Greedy Prim Algorithm using c/c++

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.


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

struct edge
{
                int from,to ;
                float cost ;
                logical rejected,selected ;
};
int nv,ne;
struct edge e[20];
void greedy_prim();
logical isnear(int j);
void main()
{
                clrscr();
                                int i ;
                cout << "No. of vertices = " ;
                cin >> nv ;
                cout << "No. of edges = " ;
                cin >> ne ;
                cout << "Enter end-vertices and cost for each edge " << endl ;
                for(i=1;i<=ne;i++)
                {
                                cout<<"\nEnter for edge: "<<i;
                                cout<<"\nEnter vertice from: ";
                                cin >> e[i].from;
                                cout<<"\nEnter vertice to: ";
                                cin>> e[i].to;
                                cout<<"\nEnter cost: ";
                                cin>> e[i].cost ;
                                e[i].rejected=FALSE ;
                                e[i].selected=FALSE ;
                }
                greedy_prim();

                float mincost=0 ;

                cout << "Edge    Cost" << endl ;
                cout << "-----  -----" << endl ;
                for(i=1;i<=ne;i++)
                {
                                if(e[i].selected)
                                {
                                                cout << "(" << e[i].from << "-" << e[i].to << ")    " ;
                                                cout << e[i].cost << endl ;
                                                mincost += e[i].cost ;
                                }
                }
                cout << "       -----" << endl ;
                cout << "Total    " << mincost << endl ;

getch();
}

void greedy_prim()
{
                int i,j,k,pos=1 ;
                float min=e[1].cost ;

                // Initialize solution

                for(i=2;i<=ne;i++)
                {
                                if(e[i].cost<min)
                                {
                                                min=e[i].cost ;
                                                pos=i ;
                                }
                }
                e[pos].selected=TRUE ;

                // Main loop starts here

                for(i=2;i<nv;i++)
                {
                                min=9999 ; pos=0 ;
                                for(j=1;j<=ne;j++)
                                {
                                                if(e[j].rejected || e[j].selected)
                                                                continue ;
                                                if(isnear(j)&&e[j].cost<min)
                                                {
                                                                min=e[j].cost ;
                                                                pos=j ;
                                                }
                                }
                                e[pos].selected=TRUE ;
                }
}


logical isnear(int j)
{
                int i ;
                logical flag1=FALSE,flag2=FALSE ;
                for(i=1;i<=ne;i++)
                {
                                if(e[i].selected)
                                {
                                                if(e[j].from==e[i].from || e[j].from==e[i].to)
                                                                flag1=TRUE ;
                                                if(e[j].to==e[i].from || e[j].to==e[i].to)
                                                                flag2=TRUE ;
                                }
                }
                if(flag1 && flag2)
                {
                                e[j].rejected=TRUE ;
                                return FALSE ;
                }
                if(flag1 || flag2)
                                return TRUE ;
                else
                                return FALSE ;
}