Search:

Submit Article

# Shortest Path using kruskal algorithm

Posted By: Anitha Hs     Category: C++ Programming     Views: 9692
` # 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; }`
Share:

Didn't find what you were looking for? Find more on Shortest Path using kruskal algorithm Or get search suggestion and latest updates.

 Anitha Hs author of Shortest Path using kruskal algorithm is from Australia. View All Articles