C++ Programming Tutorial

 
 
 
 

Image

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

 # define MAX_VERTICES  10
 # define MAX_EDGES     15


 //-------------------------------  Vertex  ------------------------------//


 class Vertex
 {
    public:
       int label;

    public:
       Vertex( )   {  }
       ~Vertex( )  {  }

       void SetVertex(const int);
 };


 //-------------------------------  Edge  --------------------------------//


 class Edge
 {
    public:
       int weight;

       Vertex V1;
       Vertex V2;

    public:
       Edge( )   { }
       ~Edge( )  { }

       void SetEdge(const Vertex,const Vertex,const int);
 };


 //----------------------------  SetVertex( )  ---------------------------//


 void Vertex::SetVertex(const int _label)
 {
    label=_label;
 }


 //-----------------------------  SetEdge( )  ----------------------------//


 void Edge::SetEdge(const Vertex _V1,const Vertex _V2,const int _weight)
 {
    V1=_V1;
    V2=_V2;

    weight=_weight;
 }

 int main( )
 {
    clrscr( );
    textmode(BW80);

    /***************************************************************

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

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

    cout<<endl;

    int v1;
    int v2;
    int weight;

    cout<<\" **********  Edges and their Weights  ********* \"<<endl;

    for(count=0;count<edges;count++)
    {
       cout<<\"    ----------       ---------->\";

       gotoxy(2,wherey( ));
       cin>>v1;

       gotoxy(35,(wherey( )-1));
       cin>>v2;

       gotoxy(17,(wherey( )-1));
       cin>>weight;

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

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

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

       E[count].SetEdge(V[(v1-1)],V[(v2-1)],weight);
    }

    cout<<endl<<\"Press any key to Apply PRIMS Algorithm...\";

    getch( );
    clrscr( );

    int U[MAX_VERTICES]={0};
    int vertex_1[MAX_VERTICES]={0};
    int vertex_2[MAX_VERTICES]={0};
    int edge_weights[MAX_VERTICES]={0};
    int resultant_weights[MAX_VERTICES]={0};

    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) )
         {
        resultant_weights[(u_count-2)]=E[i].weight;

        break;
         }
      }
       }

       else
      break;
    }
    while(1);

    cout<<\"*******************  Input  ********************\"<<endl;
    cout<<\" V = { \";

    for(count=1;count<vertices;count++)
       cout<<count<<\",\";

    cout<<count<<\" } \"<<endl;

    cout<<\" E = { \";

    for(count=0;count<edges;count++)
    {
       cout<<\"(\"<<(E[count].V1.label+1)<<\",\"<<(E[count].V2.label+1)<<\")\";

       if(count<(edges-1))
      cout<<\",\";
    }

    cout<<\" } \"<<endl<<endl;

    cout<<\"*******************  Result  ********************\"<<endl;
    cout<<\" U = { \";

    for(count=0;count<(u_count-1);count++)
       cout<<(U[count]+1)<<\",\";

    cout<<(U[count]+1)<<\" }\"<<endl;
    cout<<\" Total Cost = \";

    int cost=0;

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

       if(count<(u_count-2))
      cout<<resultant_weights[count]<<\"+\";
    }

    cout<<resultant_weights[(count-1)]<<\" =  \"<<cost<<endl<<endl;

    cout<<endl<<\" Press any Key to Exit...\";

    getch( );
    return 0;
 }

    Related Post:
  1. Program to illustrate the implementation of Y-Direction Shear Transformation

  2. Program to illustrate pointers and an array of structure

  3. Program to estimate the value of Second Derivative of the function at the given points from the given data using Central Difference Formula of order 2

  4. Program of rotate about reference point

  5. Program of calculator

  6. Program to show the Urdu Alphabets using Stroke Method

  7. Program to illustrate the implementation of Rotation Transformation along a Pivot Point

  8. Program that displays the size, address of the variables of type int , float and char.

  9. Program to illustrate the use of inline functions

  10. File Operation Program

  11. Program to help Umar in this task. Represent each city by one lowercase character. Thus, you can have at most 26 different cities to visit....

  12. Program that reads marks obtained by a student in a test of 100 marks and computes his grade

  13. Program to illustrate friend function

  14. Program that prints odd numbers form 0 to 50 (Using for Loop)

  15. Program to find the day of a week of a given date from 15 october 1582 to end of universe using arrays

  16. Program to illustrate the difference b/w passing the whole array and the single array element as a parameter to a function

  17. Program to illustrate template classes

  18. Program that reads marks obtained by a student in a test of 100 marks and computes his grade

  19. Program to capitalize the first charcter of every word in a string

  20. Program that reads a number and prints even if the number is even and prints odd if the number is odd.