Logo 
Search:

C++ Programming Articles

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

Program to implement the Prim's Algorithm to solve Minimum Spanning Tree Problem (MST) using Graphics and with Mouse support

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

A C++ Program to implement the Prim's Algorithm to solve Minimum Spanning Tree Problem (MST) using Graphics and with Mouse support.

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


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

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

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

 /*************************************************************************//*************************************************************************///-------------------  Class Function Definitions  ----------------------///*************************************************************************//*************************************************************************//*************************************************************************///----------------------------  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)
 {
    char Number[10]={NULL};

    itoa(number,Number,10);

    moveto(x,y);

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

 /*************************************************************************//*************************************************************************///------------------------------  main( )  ------------------------------///*************************************************************************//*************************************************************************/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(139,6,"*****  Prim's Algorithm  *****");
    outtextxy(140,6,"*****  Prim's Algorithm  *****");
    outtextxy(140,7,"*****  Prim'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 Prim'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 Prim's Algorithm...");

    ShowMouseCursor( );

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

    int U[MAX_VERTICES];
    int vertex_1[MAX_VERTICES];
    int vertex_2[MAX_VERTICES];
    int edge_weights[MAX_VERTICES];
    int resultant_weights[MAX_VERTICES];

    int flag_1=0;
    int flag_2=0;
    int u_count=1;
    int temp_vertex=0;
    int temp_vertex_1=0;
    int temp_vertex_2=0;
    int lowest_edge_weight=0;

    U[0]=0;

    do
    {
       count=0;

       for(int i=0;i<vertices;i++)
       {
      vertex_1[i]=0;
      vertex_2[i]=0;
      edge_weights[i]=0;
       }

       for(i=0;i<u_count;i++)
       {
      flag_1=0;

      for(int j=0;j<edges;j++)
      {
         if(E[j].V1.label==U[i] || E[j].V2.label==U[i])
         {
        flag_2=0;

        if(E[j].V1.label!=U[i])
        {
           temp_vertex=E[j].V1.label;
           temp_vertex_1=E[j].V2.label;
        }

        else
        {
           temp_vertex=E[j].V2.label;
           temp_vertex_1=E[j].V1.label;
        }

        for(int k=0;k<u_count;k++)
        {
           if(temp_vertex==U[k])
           {
              flag_2=-1;

              break;
           }
        }

        if(flag_2!=-1)
        {
           if(flag_1==0 || lowest_edge_weight>E[j].weight)
           {
              lowest_edge_weight=E[j].weight;
              temp_vertex_2=temp_vertex;
              flag_1=1;
           }
        }
         }
      }

      if(flag_1==1)
      {
         vertex_2[count]=temp_vertex_2;
         vertex_1[count]=temp_vertex_1;
         edge_weights[count]=lowest_edge_weight;

         count++;
      }
       }

       flag_1=0;

       for(i=0;i<count;i++)
       {
      if(flag_1==0 || lowest_edge_weight>edge_weights[i])
      {
         lowest_edge_weight=edge_weights[i];
         temp_vertex_1=vertex_1[i];
         temp_vertex_2=vertex_2[i];
         flag_1=1;
      }
       }

       if(flag_1==1)
       {
      U[u_count]=temp_vertex_2;
      u_count++;

      for(i=0;i<edges;i++)
      {
         if((E[i].V1.label==temp_vertex_1
                    && E[i].V2.label==temp_vertex_2) ||
        (E[i].V1.label==temp_vertex_2
                    && E[i].V2.label==temp_vertex_1) )
         {
        E[i].ShowEdge( );
        resultant_weights[(u_count-2)]=E[i].weight;

        settextstyle(2,0,4);

        HideMouseCursor( );

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

        break;
         }
      }
       }

       elsebreak;
    }
    while(1);

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

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

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

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

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

    for(count=0;count<u_count;count++)
    {
       PrintText((getx( )+3),gety( ),(U[count]+1));

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

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

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

    int cost=0;

    for(count=0;count<(u_count-1);count++)
    {
       cost+=resultant_weights[count];

       PrintText((getx( )+3),gety( ),resultant_weights[count]);

       if(count<(u_count-2))
       {
      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 Prim's Algorithm to solve Minimum Spanning Tree Problem (MST) using Graphics and 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].

 
Vijay Butani from Australia Comment on: Mar 05
i want to disable the taskmanager using c program

View All Comments