# include <iostream.h> # include <stdlib.h> # include <conio.h> # define MAX_VERTICES 10 # define MAX_EDGES 15 //------------------------------- Vertex ------------------------------// class Vertex { public: int label; public: Vertex( ) { } ~Vertex( ) { } void SetVertex(const int); }; //------------------------------- Edge --------------------------------// class Edge { public: int weight; Vertex V1; Vertex V2; public: Edge( ) { } ~Edge( ) { } void SetEdge(const Vertex,const Vertex,const int); }; //---------------------------- SetVertex( ) ---------------------------// void Vertex::SetVertex(const int _label) { label=_label; } //----------------------------- SetEdge( ) ----------------------------// void Edge::SetEdge(const Vertex _V1,const Vertex _V2,const int _weight) { V1=_V1; V2=_V2; weight=_weight; } int main( ) { clrscr( ); textmode(BW80); /*************************************************************** 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]; for(int count=0;count<vertices;count++) V[count].SetVertex(count); int v1; int v2; int weight; cout<<\"\\n ********** Edges and their Weights ********* \"<<endl; for(count=0;count<edges;count++) { cout<<\" ---------- ---------->\"; gotoxy(2,wherey( )); cin>>v1; gotoxy(35,(wherey( )-1)); cin>>v2; gotoxy(17,(wherey( )-1)); cin>>weight; v1=((v1<1)?1:v1); v1=((v1>vertices)?vertices:v1); v2=((v2<1)?1:v2); v2=((v2>vertices)?vertices:v2); weight=((weight<=0)?0:weight); E[count].SetEdge(V[(v1-1)],V[(v2-1)],weight); } cout<<endl<<\"Press any key to Apply Kruskal\'s Algorithm...\"; getch( ); clrscr( ); cout<<\"******************* Input ********************\"<<endl; cout<<\" V = { \"; for(count=1;count<vertices;count++) cout<<count<<\",\"; cout<<count<<\" } \"<<endl; cout<<\" E = { \"; for(count=0;count<edges;count++) { cout<<\"(\"<<(E[count].V1.label+1)<<\",\"<<(E[count].V2.label+1)<<\")\"; if(count<(edges-1)) cout<<\",\"; } cout<<\" } \"<<endl<<endl; 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_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; } } } } } } } } } } 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<<endl<<endl; cout<<endl<<\" Press any Key to Exit...\"; getch( ); return 0; }