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, (V
_{2} in an edge V_{1} → V_{2}) 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..! **Commenting is super easy if you are a Facebook, Twitter or a Google+ user**…! So, don’t hesitate..! 😉 … Keep practising..! Happy Coding..! 😀

### Like this:

Like Loading...

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

LikeLike

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

LikeLike

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

LikeLike

Pingback: graph theory | programmingalgos