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 help Umar in this task. Represent each city by one lowercase character. Thus, you can have at most 26 different cities to visit....

  2. Program that performs addition of 2 matrix using friend function

  3. Program to estimate value of First Derivative of the function at the given points from the given data using Backward Difference Formula , Forward diff

  4. Program of class and objects using private and public data members

  5. Program to illustrate the implementation of Scaling Transformation along a Fixed Point

  6. Program of Midpoint Circle Drawing

  7. Program to show the implementation of None-or-All Character Clipping Strategy (Text Clipping Example)

  8. Program that sorts numbers using topological sort method

  9. Program of constructor overloading

  10. Program to illustrate the binary operator(+) overloading by creating a new object

  11. Program of simple example of class and object

  12. Program to implement Add and Subtract function on Big Number Class

  13. Program of Deapth First Search Traversal ( DFS )

  14. Program to show the implementation of None-or-All String Clipping Strategy (Text Clipping Example)

  15. Program of that provides an example of function overloading

  16. Program to create a stack using dynamic memory allocation

  17. Program that find the distance between two points in 2D and 3D space using function overloading

  18. Program that computes and displays the factorial of the given number using recursion

  19. Program to estimate the value of Third Derivative of the function at the given points from the given data using Central Difference Formula of Order 4

  20. Program to construct Natural Cubic Spline Interpolant from the given data