Wednesday, 26 April 2017

Implementation of Weighted Graph using STL

In this post we are discussing how to implement weighted graph using STL. Program is also given below. In this program we used an array of vectors of pair vectors. vector is an sequence container which is used to store adjacency list of the graph. Pair is also a container to store the pair of elements in which first element is destination of the edge and second element is weight of the edge connecting the u node to v node. See the example given below

Example:



vector< pair<int,int> > adj_list[5]

The statement adj_list[1].push_back(make_pair(2,100) means that vertex 1 is connected to vertex 2 by an edge of weight 500. The above example is implemented and executed in the program given below.


PROGRAM TO IMPLEMENT WEIGHTED GRAPH USING STL:

#include <stdio.h>
#include <vector>
using namespace std;
int main()
{
  int n;
  printf("\nEnter the number of vertices: \n");
  scanf("%d",&n);

  std::vector< pair<int,int> > adj_list[n+1];
  std::vector< pair<int,int> >::iterator it;
  int destination,weight;

  for(int i=1;i<=n;i++)
  {
     int edges;
          printf("\n\nEnter the number of edges from vertex %d: ",i);
          scanf("%d",&edges);
          if(edges!=0)
          {
             for(int j=1;j<=edges;j++)
             {
                printf("\nEnter the destination and weight of edge %d: ",j);
                {
                  scanf("%d%d",&destination,&weight);
                  adj_list[i].push_back(make_pair(destination,weight));

                }
             }
          }
  }

  /* Printing implemented Graph */

  printf("\n\nImplemented Graph is: \n");

  for(int i=1;i<=n;i++)
  {
      printf("\n\n");
      for(it=adj_list[i].begin();it!=adj_list[i].end();it++)
      {
            destination=it->first;
            weight=it->second;
                 printf("\nNode %d is connected to Node %d with weight = %d",i,destination,weight);
      }
  }

     return 0;
}


OUTPUT:

 


EmoticonEmoticon