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, (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..! Keep practicing..! Happy Coding..! 😀

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

Hi, sorry for the late reply. I created a new post for that, you’ll find the code there 🙂

http://theoryofprogramming.com/2017/12/31/adjacency-list-string-vertices-using-c-stl/

Nice.

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

adjacencyList[v1].push_back(make_pair(v2, weight));

adjancencyList[v2].push_back(make_pair(v1,weight));

}

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 🙂

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

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;

}

// your code goes here

return 0;

}

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

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

Both are O(1)

Pingback: Graph Theory Basics

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

please guide me

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?

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.

Awesome simple implementation

Thank you! 🙂

Thank you so very much.

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

Thanks and great code 🙂

An advice use the C++ methods (cout, cin) instead of C functions

http://stackoverflow.com/questions/2872543/printf-vs-cout-in-c

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

Thanks a lot.!! 😀

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

Each push back operation in the C++ STL List takes O(1) time… It is actually implemented as a doubly linked list… 😉

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 🙂

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

What is v1 and v2 here?

They are two vertices between which there’s an edge. V

_{1}→ V_{2}It is the source and destination vertices connected by a single edge with weight ‘weight’

compact and easy to under stand – great job

Thanks a lot 😀

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

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

Pingback: graph theory | programmingalgos