Logo 
Search:

C++ Programming Articles

Submit Article
Home » Articles » C++ Programming » Computer GraphicsRSS Feeds

Program to implement the Kurskal's Algorithm to solve Minimum Cost Spanning Tree Problem (MST) using Graphics

Posted By: Easy Tutor     Category: C++ Programming     Views: 29660

A C++ Program to implement the Kurskal's Algorithm to solve Minimum Cost Spanning Tree Problem (MST) using Graphics.

Code for Program to implement the Kurskal's Algorithm to solve Minimum Cost Spanning Tree Problem (MST) using Graphics in C++ Programming

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

 /*************************************************************************///----------------------------  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);
 }


 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: 



Easy Tutor
Easy Tutor author of Program to implement the Kurskal's Algorithm to solve Minimum Cost Spanning Tree Problem (MST) using Graphics is from United States. Easy Tutor says

Hello Friends,

I am Free Lance Tutor, who helped student in completing their homework.

I have 4 Years of hands on experience on helping student in completing their homework. I also guide them in doing their final year projects.

I have share many programs on this website for everyone to use freely, if you need further assistance, than please contact me on easytutor.2ya [at the rate] gmail [dot] com

I have special discount scheme for providing tutor services. I am providing tutor service to students from various contries, currently most of my students are from United States, India, Australia, Pakistan, Germany, UK and Canada.

I am also here to expand my technical network to receive more opportunity in my career, make friends to help them in resolving their technical problem, learn and share my knowledge, If you like to be my friend, Please send me friend request.

Thanks,
Happy Programming :)

 
View All Articles

 
Please enter your Comment

  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].

 
No Comment Found, Be the First to post comment!