# include <iostream.h>
# include <graphics.h>
# include <stdlib.h>
# include <conio.h>
# define MAX_VERTICES 10
# define MAX_EDGES 15
/*************************************************************************///------------------------------- Vertex ------------------------------///*************************************************************************/class Vertex
{
public:
int x;
int y;
int label;
private:
char Label[5];
public:
Vertex( ) { }
~Vertex( ) { }
void SetVertex(constint,constint,constint);
void ShowVertex( );
};
/*************************************************************************///------------------------------- Edge --------------------------------///*************************************************************************/class Edge
{
public:
int weight;
Vertex V1;
Vertex V2;
private:
char Weight[5];
public:
Edge( ) { }
~Edge( ) { }
void SetEdge(const Vertex,const Vertex,constint);
void ShowEdge( );
};
/*************************************************************************//*************************************************************************///------------------------ Function Definitions -----------------------///*************************************************************************//*************************************************************************//*************************************************************************///---------------------------- SetVertex( ) ---------------------------///*************************************************************************/void Vertex::SetVertex(constint _x,constint _y,constint _label)
{
x=_x;
y=_y;
label=_label;
itoa((label+1),Label,10);
}
/*************************************************************************///---------------------------- ShowVertex( ) --------------------------///*************************************************************************/void Vertex::ShowVertex( )
{
setcolor(1);
setfillstyle(1,1);
pieslice(x,y,0,360,10);
setcolor(9);
circle(x,y,10);
setcolor(15);
settextstyle(2,0,4);
if(label<9)
outtextxy((x-2),(y-6),Label);
elseif(label>=9)
outtextxy((x-5),(y-6),Label);
}
/*************************************************************************///----------------------------- SetEdge( ) ----------------------------///*************************************************************************/void Edge::SetEdge(const Vertex _V1,const Vertex _V2,constint _weight)
{
V1=_V1;
V2=_V2;
weight=_weight;
itoa(weight,Weight,10);
}
/*************************************************************************///---------------------------- ShowEdge( ) ----------------------------///*************************************************************************/void Edge::ShowEdge( )
{
setlinestyle(0,0,3);
setcolor(11);
line(V1.x,V1.y,V2.x,V2.y);
setlinestyle(0,0,0);
V1.ShowVertex( );
V2.ShowVertex( );
int x=(((V1.x+V2.x)/2)-6);
int y=(((V1.y+V2.y)/2)-8);
setcolor(12);
settextstyle(2,0,7);
outtextxy(x,y,Weight);
outtextxy((x+1),y,Weight);
outtextxy((x+1),(y+1),Weight);
}
/*************************************************************************//*************************************************************************///------------------------------ main( ) ------------------------------///*************************************************************************//*************************************************************************/int main( )
{
textmode(C4350);
int driver=VGA;
int mode=VGAHI;
int error_code;
initgraph(&driver,&mode,"..\\Bgi");
error_code=graphresult( );
if(error_code!=grOk)
{
restorecrtmode( );
textmode(BW80);
clrscr( );
cout<<" \n Fatal Error : Graphic Driver not initialized"<<endl;
cout<<" Error Reason : "<<grapherrormsg(error_code)<<endl;
cout<<" \n Press any key to exit...";
getch( );
exit(1);
}
/*************************************************************** Sample Input ************ Vertices , Edges 6 , 10 Vertex_1 , Vertex_2 320 , 100 170 , 200 320 , 250 470 , 200 220 , 400 420 , 400 Vertxe_1 ----> Vertex_2 , Weight 1 ----> 2 , 6 1 ----> 4 , 5 1 ----> 3 , 1 2 ----> 3 , 5 2 ----> 5 , 3 3 ----> 5 , 6 3 ----> 6 , 4 3 ----> 4 , 5 4 ----> 5 , 2 5 ----> 5 , 6 Answer : 15 ***************************************************************/int vertices=0;
int edges=0;
cout<<"******************* Input ********************"<<endl;
cout<<"Enter the Total Number of Vertices (1-10) = ";
cin>>vertices;
vertices=((vertices<1)?1:vertices);
vertices=((vertices>10)?10:vertices);
cout<<"Enter the Total Number of Edges (1-15) = ";
cin>>edges;
edges=((edges<0)?0:edges);
edges=((edges>15)?15:edges);
Vertex V[MAX_VERTICES];
Edge E[MAX_EDGES];
cleardevice( );
setcolor(15);
rectangle(45,85,595,415);
int x;
int y;
for(int count=0;count<vertices;count++)
{
gotoxy(1,1);
cout<<"******* XY-Coordinates of Vertex-"<<(count+1)<<" *******";
gotoxy(1,2);
cout<<"Enter value of x-coordinate (060-580) = ";
cin>>x;
x=((x<60)?60:x);
x=((x>580)?580:x);
gotoxy(1,3);
cout<<"Enter value of y-coordinate (100-400) = ";
cin>>y;
y=((y<100)?100:y);
y=((y>400)?400:y);
V[count].SetVertex(x,y,count);
V[count].ShowVertex( );
gotoxy(1,1);
cout<<" ";
gotoxy(1,2);
cout<<" ";
gotoxy(1,3);
cout<<" ";
}
gotoxy(1,28);
cout<<" V = { ";
for(count=1;count<vertices;count++)
cout<<count<<",";
cout<<count<<" } ";
gotoxy(1,30);
cout<<" E = { ";
x=wherex( );
int v1;
int v2;
int weight;
for(count=0;count<edges;count++)
{
gotoxy(1,1);
cout<<"****** Vertex Numbers for Edge-"<<(count+1)<<" ******";
gotoxy(1,2);
cout<<"Enter the Vertice-1 (1-"<<vertices<<") = ";
cin>>v1;
v1=((v1<1)?1:v1);
v1=((v1>vertices)?vertices:v1);
gotoxy(1,3);
cout<<"Enter the Vertice-2 (1-"<<vertices<<") = ";
cin>>v2;
v2=((v2<1)?1:v2);
v2=((v2>vertices)?vertices:v2);
gotoxy(1,4);
cout<<"Enter the Edge Weight = ";
cin>>weight;
weight=((weight<=0)?0:weight);
E[count].SetEdge(V[(v1-1)],V[(v2-1)],weight);
E[count].ShowEdge( );
gotoxy(x,30);
cout<<"("<<v1<<","<<v2<<")";
if(count<(edges-1))
cout<<",";
x=wherex( );
gotoxy(1,1);
cout<<" ";
gotoxy(1,2);
cout<<" ";
gotoxy(1,3);
cout<<" ";
gotoxy(1,4);
cout<<" ";
}
gotoxy(x,30);
cout<<" } ";
getch( );
cleardevice( );
gotoxy(5,3);
cout<<" ******************** Applying PRIMS Algorithm ********************";
setcolor(15);
rectangle(45,85,595,415);
for(count=0;count<vertices;count++)
V[count].ShowVertex( );
int U[MAX_VERTICES];
int vertex_1[MAX_VERTICES];
int vertex_2[MAX_VERTICES];
int edge_weights[MAX_VERTICES];
int resultant_weights[MAX_VERTICES];
int flag_1=0;
int flag_2=0;
int u_count=1;
int temp_vertex=0;
int temp_vertex_1=0;
int temp_vertex_2=0;
int lowest_edge_weight=0;
U[0]=0;
do
{
count=0;
for(int i=0;i<vertices;i++)
{
vertex_1[i]=0;
vertex_2[i]=0;
edge_weights[i]=0;
}
for(i=0;i<u_count;i++)
{
flag_1=0;
for(int j=0;j<edges;j++)
{
if(E[j].V1.label==U[i] || E[j].V2.label==U[i])
{
flag_2=0;
if(E[j].V1.label!=U[i])
{
temp_vertex=E[j].V1.label;
temp_vertex_1=E[j].V2.label;
}
else
{
temp_vertex=E[j].V2.label;
temp_vertex_1=E[j].V1.label;
}
for(int k=0;k<u_count;k++)
{
if(temp_vertex==U[k])
{
flag_2=-1;
break;
}
}
if(flag_2!=-1)
{
if(flag_1==0 || lowest_edge_weight>E[j].weight)
{
lowest_edge_weight=E[j].weight;
temp_vertex_2=temp_vertex;
flag_1=1;
}
}
}
}
if(flag_1==1)
{
vertex_2[count]=temp_vertex_2;
vertex_1[count]=temp_vertex_1;
edge_weights[count]=lowest_edge_weight;
count++;
}
}
flag_1=0;
for(i=0;i<count;i++)
{
if(flag_1==0 || lowest_edge_weight>edge_weights[i])
{
lowest_edge_weight=edge_weights[i];
temp_vertex_1=vertex_1[i];
temp_vertex_2=vertex_2[i];
flag_1=1;
}
}
if(flag_1==1)
{
U[u_count]=temp_vertex_2;
u_count++;
for(i=0;i<edges;i++)
{
if((E[i].V1.label==temp_vertex_1 && E[i].V2.label==temp_vertex_2) ||
(E[i].V1.label==temp_vertex_2 && E[i].V2.label==temp_vertex_1) )
{
E[i].ShowEdge( );
resultant_weights[(u_count-2)]=E[i].weight;
gotoxy(48,28);
cout<<"Press any Key to Continue...";
getch( );
gotoxy(48,28);
cout<<" ";
break;
}
}
}
elsebreak;
}
while(1);
gotoxy(1,1);
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
cout<<" "<<endl;
gotoxy(1,1);
cout<<"******************* Result ********************"<<endl;
cout<<" U = { ";
for(count=0;count<(u_count-1);count++)
cout<<(U[count]+1)<<",";
cout<<(U[count]+1)<<" }"<<endl<<endl;
cout<<" Total Cost = ";
int cost=0;
for(count=0;count<(u_count-1);count++)
{
cost+=resultant_weights[count];
if(count<(u_count-2))
cout<<resultant_weights[count]<<"+";
}
cout<<resultant_weights[(count-1)]<<" = "<<cost;
gotoxy(54,28);
cout<<"Press any Key to Exit.";
getch( );
closegraph( );
return 0;
}