# 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.
```/*
* 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
}

for (int i = 1; i < adjacencyList.size(); ++i) {

list< pair<int, int> >::iterator itr = adjacencyList[i].begin();

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

## 38 thoughts on “Adjacency List using C++ STL”

1. den

How to make the vertices refer to a string and not to int ?

2. Nice.

3. Rahul_Rajput

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

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

• 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);

}

4. Raphael

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

• No, not yet. Will make a post on it soon 🙂

5. Tushar

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 ??

6. This code results with Runtime Error since the index of vector is the maximum value of a vertex.The leads with an Runtime error

• #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;
}
return 0;
}

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

7. what is the complexity of make_pair and adjacencyList.size()

• Both are O(1)

8. Pingback: Graph Theory Basics

9. miller

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

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?

11. sreekar

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.

• I wanted it to resemble an adjacency list. We visualize an adjacency list as an array of linked lists. To mimic that I used a vector of lists.

12. MayankS

Awesome simple implementation

13. maestro_was_here

hey great job..both of you…Keep up the great work!!!

• Thanks a lot.!! 😀

14. Rishabh

Is Insertion in the list takes O(E) because you are using push_back

15. hanifi demirel

Why did you use printf and scanf?

• I’m not much into C++ myself… So I generally prefer printf and scanf… You could use cout and cin without any issues 🙂

• shivam gohel

and one reason is that scanf and printf are faster than cin and cout…

16. Pinak

What is v1 and v2 here?

• They are two vertices between which there’s an edge. V1 → V2

• It is the source and destination vertices connected by a single edge with weight ‘weight’

17. Chris Bishop

compact and easy to under stand – great job

• Thanks a lot 😀

18. I got it, because it’s in scanf the C way. sorry I got confused, I usually use cin/cout

• Everybody gets confused… 😉 … I am more used to printf() and scanf()… Let me know if you have any more doubts…! 😀

19. Why did you use references when calling to input edges and vertices?

20. Pingback: graph theory | programmingalgos