Program Shortest Path using Kruskal algorithm in cpp

The following program illustrates Kruskal algorithm in cpp to find Shortest Path.

 

 #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;
}

 

Leave a Reply