# include <iostream.h> # include <graphics.h> # include <string.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(const int,const int,const int); 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,const int); void ShowEdge( ); }; //---------------------------- SetVertex( ) ---------------------------// void Vertex::SetVertex(const int _x,const int _y,const int _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); else if(label>=9) outtextxy((x-5),(y-6),Label); } //----------------------------- SetEdge( ) ----------------------------// void Edge::SetEdge(const Vertex _V1,const Vertex _V2,const int _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); } 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 Kruskal\'s Algorithm *******************\"<<endl; setcolor(15); rectangle(45,85,595,415); for(count=0;count<vertices;count++) V[count].ShowVertex( ); for(int i=0;i<edges;i++) { for(int j=0;j<(edges-1);j++) { if(E[j].weight>=E[(j+1)].weight) { Edge Temp; Temp=E[j]; E[j]=E[(j+1)]; E[(j+1)]=Temp; } } } int e_count=0; int cycle_flag=0; Edge _E[MAX_EDGES]; int mst[MAX_VERTICES][MAX_VERTICES]={0}; for(i=0;i<=vertices;i++) { mst[i][0]=i; for(int j=1;j<vertices;j++) mst[i][j]=-1; } for(count=0;count<edges;count++) { cycle_flag=0; for(i=1;i<vertices;i++) { if(mst[E[count].V1.label][i]==E[count].V2.label || mst[E[count].V2.label][i]==E[count].V1.label) cycle_flag=1; } if(!cycle_flag) { _E[e_count]=E[count]; _E[e_count].ShowEdge( ); e_count++; for(i=1;i<vertices;i++) { if(mst[E[count].V1.label][i]==E[count].V2.label) break; if(mst[E[count].V1.label][i]==-1) { mst[E[count].V1.label][i]=E[count].V2.label; break; } } for(i=1;i<vertices;i++) { if(mst[E[count].V2.label][i]==E[count].V1.label) break; if(mst[E[count].V2.label][i]==-1) { mst[E[count].V2.label][i]=E[count].V1.label; break; } } for(i=0;i<vertices;i++) { for(int j=0;j<vertices;j++) { for(int k=1;k<vertices;k++) { if(mst[j][k]!=-1) { for(int l=1;l<vertices;l++) { if(mst[mst[j][k]][l]!=-1) { for(int m=0;m<vertices;m++) { if(mst[mst[j][k]][l]==mst[j][m]) break; if(mst[j][m]==-1) { mst[j][m]=mst[mst[j][k]][l]; break; } } } } } } } } gotoxy(48,28); cout<<\"Press any Key to Continue...\"; getch( ); gotoxy(48,28); cout<<\" \"; } } gotoxy(1,1); cout<<\" \"<<endl; cout<<\" \"<<endl; cout<<\" \"<<endl; cout<<\" \"<<endl; cout<<\" \"<<endl; gotoxy(1,1); cout<<\"******************* Result ********************\"<<endl; cout<<\" V = { \"; for(count=1;count<vertices;count++) cout<<count<<\",\"; cout<<count<<\" }\"<<endl<<\" E = { \"; for(count=0;count<(e_count-1);count++) cout<<\"(\"<<(_E[count].V1.label+1)<<\",\"<<(_E[count].V2.label+1)<<\"),\"; cout<<\"(\"<<(_E[count].V1.label+1)<<\",\"<<(_E[count].V2.label+1)<<\") }\"<<endl; cout<<\" Total Cost = \"; int cost=0; for(count=0;count<e_count;count++) { cost+=_E[count].weight; if(count<(e_count-1)) cout<<_E[count].weight<<\"+\"; } cout<<_E[count-1].weight<<\" = \"<<cost; gotoxy(54,28); cout<<\"Press any Key to Exit.\"; getch( ); return 0; }