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 the 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);
	return 0;

Feel free to comment if you have any doubts..! Commenting is super easy if you are a Facebook, Twitter or a Google+ user…! So, don’t hesitate..! 😉 … Keep practising..! Happy Coding..! 😀

4 thoughts on “Adjacency List using C++ STL

  1. Pingback: graph theory | programmingalgos

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s