Adjacency List using C++ STL

Hello people..! This is a special extension for my discussion on Graph Theory Basics. Here, I give you the code for implementing the Adjacency List using C++ STL. Some of the features of this code are –

  • The Adjacency List is a vector of list, where each element is a pair, from the utility header file. This pair stores two values, the destination vertex, (V2 in an edge V1 → V2) and the weight of the edge.
  • For adding an edge, all we have to do is to call push_back() function. Although it does not represent our addEdge() in the initial discussion where we had head insertion, it is tail insertion which is an O(1) insertion operation.
  • The vector representing the vertices is 1-indexed.
/*
 * Adjacency List for
 * Directed Weighted Graph
 * Code using C++ STL
 * 
 * Authored by,
 * Vamsi Sangam.
 *
 */

#include <cstdio>
#include <vector>
#include <list>
#include <utility>

using namespace std;

int main()
{
	int vertices, edges, v1, v2, weight;
	
	printf("Enter the Number of Vertices -\n");
	scanf("%d", &vertices);
	
	printf("Enter the Number of Edges -\n");
	scanf("%d", &edges);
	
	// Adjacency List is a vector of list.
	// Where each element is a pair<int, int>
	// pair.first -> the edge's destination
	// pair.second -> edge's weight
	vector< list< pair<int, int> > > adjacencyList(vertices + 1);
	
	printf("Enter the Edges V1 -> V2, of weight W\n");
	
	for (int i = 1; i <= edges; ++i) {
		scanf("%d%d%d", &v1, &v2, &weight);
		
		// Adding Edge to the Directed Graph
		adjacencyList[v1].push_back(make_pair(v2, weight));
	}
	
	printf("\nThe Adjacency List-\n");
	// Printing Adjacency List
	for (int i = 1; i < adjacencyList.size(); ++i) {
		printf("adjacencyList[%d] ", i);
		
		list< pair<int, int> >::iterator itr = adjacencyList[i].begin();
		
		while (itr != adjacencyList[i].end()) {
			printf(" -> %d(%d)", (*itr).first, (*itr).second);
			++itr;
		}
		printf("\n");
	}
	
	return 0;
}

Feel free to comment if you have any doubts..! Keep practicing..! Happy Coding..! 😀

39 thoughts on “Adjacency List using C++ STL”

  3. How to make adjacency list if there are two weights are related to every single edge in an undirected graph?

    Reply

    1. Then instead of that pair, you could use a list, or you could use a pair where the second element of the pair is another pair. It will make the code complicated though. So I guess it would be better if you’d use an adjacency matrix in your case, by making the graph a 3D array.

      Reply

      1. In case of a undirected graph , cant we just push back the values for both the nodes eg:

        for (int i = 1; i <= edges; ++i)
        {
        scanf("%d%d%d", &v1, &v2, &weight);

        adjacencyList[v1].push_back(make_pair(v2, weight));
        adjancencyList[v2].push_back(make_pair(v1,weight));
        }

        Reply

  4. Hello very usefull your code, thanks fella. Do you have the code to create a topological sort from the adjacency list please?

    Reply

  5. Hello Vamsi. I want to do Graph programming using STL ( Graph library file ) But it is not available by default . So I installed LEMON graph library but I am not able to configure it so getting error like graph.h : no such file. Could u help me in that or will u suggest any other graph library file ??

    Reply

    1. #include
      #include
      #include
      using namespace std;

      int main() {
      int v,e,i,v1,source,destination;
      cin>>v>>e;
      vector<list > graph(v);
      for(i=0;i>v1;
      graph[i].push_back(v1);
      }
      for(i=0;i>source>>destination;
      list::iterator it=graph[i].begin();
      if(*it==source)
      {

      graph[i].push_back(destination);
      }
      }

      for(i=0;i<graph.size();i++)
      {

      list::iterator itf=graph[i].begin();
      while(itf!=graph[i].end())
      {
      cout<<*itf<<" ";
      itf++;
      }
      cout<<endl;
      }
      // your code goes here
      return 0;
      }

      check this out you will come to know where you made a mistake.Thank You

      Reply
  8. Pingback: Graph Theory Basics

  9. If I want to create such an algorithm with adjacency matrix instead adjacent list which must either change to the program
    please guide me

    Reply

  10. In this case, if I resolve put values without order, like 1 -> 5, 8 -> 2. The algorithm will try access adjacencyList[4] and this will cause a segmentation fault, no?

    Reply

  11. Is there a special reason you used a list instead of a vector as a inner container to the outer vector? As far as i know vector<vector<pair > > adjacencyList(noOfVertices + 1) would also work.

    Reply
  20. Pingback: graph theory | programmingalgos

Leave a Reply