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..! 😀

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

  1. Pingback: graph theory | programmingalgos

  10. 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

  11. 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

  12. 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
  13. Pingback: Graph Theory Basics

    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

  16. 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

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

    Reply

  18. 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

    2. hey den,
      you can use unordered_map instead of vector.

      unordered_map< string, list <pair> > AdjList;

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *