Logo 
Search:

C++ Programming Articles

Submit Article
Home » Articles » C++ Programming » Mouse ProgrammingRSS Feeds

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

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

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

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


 # include <iostream.h>
 # include <graphics.h>
 # include   <string.h>
 # include   <stdlib.h>
 # include    <conio.h>
 # include     <math.h>

 /*************************************************************************///---------------------------  User-Defined  ----------------------------///*************************************************************************/

 # include "Mouse.h"// Included in source zip file
 # include "Input.h"// Included in source zip file

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

       constint Hit( );
 };

 /*************************************************************************///-------------------------------  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( )
 {
    HideMouseCursor( );

    setcolor(1);
    setfillstyle(1,1);
      pieslice(x,y,0,360,10);

    setcolor(9);
      circle(x,y,10);
      circle(x,y,11);

    setcolor(15);
    settextstyle(2,0,4);

    if(label<9)
       outtextxy((x-2),(y-6),Label);

    elseif(label>=9)
       outtextxy((x-5),(y-6),Label);

    ShowMouseCursor( );
 }

 /*************************************************************************///--------------------------------  Hit( )  -----------------------------///*************************************************************************/constint Vertex::Hit( )
 {
    int _x=0;
    int _y=0;

    GetMousePosition(&_x,&_y);

    if(_x>=(x-10) && _x<=(x+10) && _y>=(y-10) && _y<=(y+10))
    {
       double d=sqrt(( powl((_x-x),2) + pow((_y-y),2) ));

       if(d<=10)
      return 1;
    }

    return 0;
 }

 /*************************************************************************///-----------------------------  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( )
 {
    HideMouseCursor( );

    setlinestyle(0,0,3);

    setcolor(1);
      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(11);
    settextstyle(2,0,7);
      outtextxy(x,y,Weight);
      outtextxy((x+1),y,Weight);
      outtextxy((x+1),(y+1),Weight);

    ShowMouseCursor( );
 }


 /*************************************************************************///----------------------------  PrintText( )  ---------------------------///*************************************************************************/void PrintText(constint x,constint y,constint number,constint color=15)
 {
    char Number[10]={NULL};

    itoa(number,Number,10);

    moveto(x,y);

    setcolor(color);
    settextstyle(2,0,4);
      outtext(Number);
 }


 int main( )
 {
    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);
    }

    cleardevice( );

    setcolor(15);
      rectangle(5,5,635,32);
      rectangle(5,35,635,455);
      rectangle(5,458,635,476);

    setfillstyle(1,7);
      bar(6,6,634,31);

    setfillstyle(1,8);
      bar(6,459,634,475);
      bar(23,80,180,83);

    settextstyle(2,0,7);
      setcolor( 9);
    outtextxy(119,6,"*****  Kruskal's Algorithm  *****");
    outtextxy(120,6,"*****  Kruskal's Algorithm  *****");
    outtextxy(120,7,"*****  Kruskal's Algorithm  *****");

      setcolor(11);
    outtextxy(24,60,"Prerequisites:");
    outtextxy(25,60,"Prerequisites:");
    outtextxy(25,61,"Prerequisites:");

    int vertices=0;
    int edges=0;

    setcolor(15);
    settextstyle(2,0,4);
      outtextxy(25,96,"Enter the Total Number of Vertices ( 1-10 ) = ");

    vertices=atoi(GetInput(295,95,2,15,0));

    vertices=((vertices<1)?1:vertices);
    vertices=((vertices>10)?10:vertices);

    setcolor(15);
    settextstyle(2,0,4);
      outtextxy(25,115,"Enter the Total Number of Edges ( 1-15 ) = ");

    edges=atoi(GetInput(295,114,2,15,0));

    edges=((edges<0)?0:edges);
    edges=((edges>15)?15:edges);

    setfillstyle(1,8);
      bar(23,380,115,383);

    setcolor(11);
    settextstyle(2,0,7);
      outtextxy(24,360,"Read Me:");
      outtextxy(25,360,"Read Me:");
      outtextxy(25,361,"Read Me:");

    setcolor(15);
    settextstyle(2,0,4);
      outtextxy(25,390,"* Press LeftMouseKey where you want to place a Vertex.");
      outtextxy(25,405,"* To draw an Edge, Click on a Vertex and Drag the Mouse Pointer to the other Vertex and Release the");
      outtextxy(25,418,"  LeftMouseKey, then enter the Weight of the Edge.");

    setcolor(14);
    settextstyle(2,0,4);
      outtextxy(15,461,"Press any Key to Continue...");

    getch( );

    setfillstyle(0,1);
      bar(6,36,634,454);

    setfillstyle(1,8);
      bar(6,459,634,475);

    setcolor(14);
    settextstyle(2,0,4);
      outtextxy(15,461,"Mark the Vertices Positions...");

    Vertex  V[MAX_VERTICES];
    Edge    E[MAX_EDGES];

    InitMouse( );
    ShowMouseCursor( );
    SetMousePosition(320,240);
    SetMouseRange(20,50,620,440);

    int x;
    int y;

    for(int count=0;count<vertices;count++)
    {
       while(!LeftMouseKeyPressed( ));

       GetMousePosition(&x,&y);

       while(LeftMouseKeyPressed( ));

       HideMouseCursor( );

       V[count].SetVertex(x,y,count);
       V[count].ShowVertex( );

       ShowMouseCursor( );
    }

    HideMouseCursor( );

    setfillstyle(1,8);
      bar(6,459,634,475);

    setcolor(14);
    settextstyle(2,0,4);
      outtextxy(15,461,"Draw the Edges and enter their weights.");

    ShowMouseCursor( );

    int i;
    int j;
    int flag=0;
    int weight;

    for(count=0;count<edges;)
    {
       flag=0;

       do
       {
      while(!LeftMouseKeyPressed( ));

      for(i=0;i<vertices;i++)
      {
         if(V[i].Hit( ) && LeftMouseKeyPressed( ))
         {
        GetMousePosition(&x,&y);

        HideMouseCursor( );

        setcolor(11);
          circle(V[i].x,V[i].y,10);

        ShowMouseCursor( );

        flag=1;
        break;
         }
      }

      if(flag)break;
       }
       while(1);

       setwritemode(1);
       setcolor(11);

       int x_end=x;
       int y_end=y;
       int prev_x=x;
       int prev_y=y;

       while(LeftMouseKeyPressed( ))
       {
      GetMousePosition(&x_end,&y_end);

      if(x_end!=prev_x || y_end!=prev_y)
      {
         HideMouseCursor( );

         line(x,y,prev_x,prev_y);
         line(x,y,x_end,y_end);

         ShowMouseCursor( );

         prev_x=x_end;
         prev_y=y_end;
      }
       }

       flag=0;

       for(j=0;j<vertices;j++)
       {
      if(V[j].Hit( ) && j!=i)
      {
         HideMouseCursor( );

         setcolor(11);
           circle(V[j].x,V[j].y,10);

         ShowMouseCursor( );

         flag=1;
         break;
      }
       }

       if(flag)
       {
      for(int k=0;k<count;k++)
      {
         if((E[k].V1.label==i && E[k].V2.label==j) ||
                      (E[k].V2.label==i && E[k].V1.label==j))
         {
        flag=0;
        break;
         }
      }
       }

       setwritemode(0);

       HideMouseCursor( );

       if(flag)
       {
      line(x,y,x_end,y_end);

      setfillstyle(1,8);
        bar(6,459,634,475);

      setcolor(15);
      settextstyle(2,0,4);
        outtextxy(15,461,"Enter the Edge Weight = ");

      weight=atoi(GetInput(145,460,3,15,8));

      setfillstyle(1,8);
        bar(6,459,634,475);

      if(count<(edges-1))
      {
         setcolor(14);
         settextstyle(2,0,4);
           outtextxy(15,461,"Draw the Edges and enter their weights.");
      }

      weight=((weight<=0)?0:weight);

      E[count].SetEdge(V[i],V[j],weight);
      count++;
       }

       setfillstyle(0,1);
     bar(6,36,634,454);

       ShowMouseCursor( );

       for(i=0;i<vertices;i++)
      V[i].ShowVertex( );

       for(i=0;i<count;i++)
      E[i].ShowEdge( );
    }

    HideMouseCursor( );

    setfillstyle(1,8);
      bar(6,459,634,475);

    setcolor(14);
    settextstyle(2,0,4);
      outtextxy(15,461,"Press any Key to apply Kruskal's Algorithm...");

    getch( );

    setfillstyle(0,1);
      bar(6,36,634,454);

    setfillstyle(1,8);
      bar(6,459,634,475);

    setcolor(15);
    settextstyle(2,0,4);
      outtextxy(15,461,"Applying Kruskals's Algorithm...");

    ShowMouseCursor( );

    for(count=0;count<vertices;count++)
       V[count].ShowVertex( );

    for(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;
                   }
                }
             }
              }
           }
        }
         }
      }

      HideMouseCursor( );

      settextstyle(2,0,4);

      do
      {
         setcolor(14);
           outtextxy(530,461,"Press any Key...");

         delay(250);

         setcolor(8);
           outtextxy(530,461,"Press any Key...");

         delay(250);
      }
      while(!kbhit( ));

      getch( );

      setfillstyle(1,8);
        bar(500,459,634,475);

      ShowMouseCursor( );
       }
    }

    HideMouseCursor( );

    setfillstyle(0,1);
      bar(6,36,634,454);

    setfillstyle(1,8);
      bar(6,459,634,475);
      bar(23,80,90,83);
      bar(23,230,122,233);

    setcolor(11);
    settextstyle(2,0,7);
      outtextxy(24,60,"Given:");
      outtextxy(25,60,"Given:");
      outtextxy(25,61,"Given:");

      outtextxy(24,210,"Solution:");
      outtextxy(25,210,"Solution:");
      outtextxy(25,211,"Solution:");

    setcolor(15);
    settextstyle(2,0,4);
      moveto(50,98);
    outtext("V = {");

    for(count=0;count<vertices;count++)
    {
       PrintText((getx( )+3),gety( ),(count+1));

       if(count<(vertices-1))
       {
      moveto((getx( )+3),gety( ));
        outtext(",");
       }
    }

    moveto((getx( )+4),gety( ));
      outtext("}");

    moveto(50,117);
      outtext("E = {");

    for(count=0;count<edges;count++)
    {
       if(count==7 || count==14)
      moveto(83,(gety( )+15));

       else
      moveto((getx( )+3),gety( ));

       outtext("(");

       PrintText((getx( )+2),gety( ),(E[count].V1.label+1));

       moveto((getx( )+2),gety( ));
     outtext(",");

       PrintText((getx( )+2),gety( ),(E[count].V2.label+1));

       moveto((getx( )+2),gety( ));
     outtext(",");

       PrintText((getx( )+2),gety( ),E[count].weight,14);

       setcolor(15);

       moveto((getx( )+2),gety( ));
     outtext(")");

       if(count<(edges-1))
       {
      moveto((getx( )+3),gety( ));
        outtext(",");
       }
    }

    moveto((getx( )+4),gety( ));
      outtext("}");

    moveto(50,248);
      outtext("E = {");

    for(count=0;count<e_count;count++)
    {
       if(e_count==7 || e_count==14)
      moveto(83,(gety( )+15));

       else
      moveto((getx( )+3),gety( ));

       outtext("(");

       PrintText((getx( )+2),gety( ),(_E[count].V1.label+1));

       moveto((getx( )+2),gety( ));
     outtext(",");

       PrintText((getx( )+2),gety( ),(_E[count].V2.label+1));

       moveto((getx( )+2),gety( ));
     outtext(",");

       PrintText((getx( )+2),gety( ),_E[count].weight,14);

       setcolor(15);

       moveto((getx( )+2),gety( ));
     outtext(")");

       if(count<(e_count-1))
       {
      moveto((getx( )+3),gety( ));
        outtext(",");
       }
    }

    moveto((getx( )+4),gety( ));
      outtext("}");

    moveto(50,267);
      outtext("Cost = ");

    int cost=0;

    for(count=0;count<e_count;count++)
    {
       cost+=_E[count].weight;

       PrintText((getx( )+3),gety( ),_E[count].weight);

       if(count<(e_count-1))
       {
      moveto((getx( )+3),gety( ));
        outtext("+");
       }
    }

    moveto((getx( )+5),gety( ));
      outtext("=");

    PrintText((getx( )+5),gety( ),cost);

    setcolor(14);
    settextstyle(2,0,4);
      outtextxy(15,461,"Press any Key to Exit.");

    getch( );
    closegraph( );
    return 0;
 }
[/Code]
  
Share: 

 
 
 


Easy Tutor
Easy Tutor author of Program to implement the Kurskal's Algorithm to solve Minimum Cost Spanning Tree Problem (MST) using Graphics with Mouse Support 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!