# 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
}

// Printing Adjacency List
for (int i = 1; i < adjacencyList.size(); ++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”

1. den says:

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

1. den says:

wow cool
now I will try to connect it with bellman-ford

2. Rahul_Rajput says:

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

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.

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

}

3. Raphael says:

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

4. Tushar says:

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

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

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

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

7. miller says:

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

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

9. sreekar says:

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.

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

10. MayankS says:

Awesome simple implementation

1. Aditya Singh Aswal says:

Thank you so very much.
Apart from lucid explanation i loved the simplicity of your website sir( http://vamsisangam.com/ )

11. maestro_was_here says:

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

12. Rishabh says:

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

13. hanifi demirel says:

Why did you use printf and scanf?

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

2. shivam gohel says:

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

14. Pinak says:

What is v1 and v2 here?

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

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

15. Chris Bishop says:

compact and easy to under stand – great job

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

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

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