Graph Implementation in C++ using STL

Given an undirected or a directed graph, implement the graph using any data structure provided by any programming language library (e.g. STL in C++, Collections in Java, etc). Implement for both weighted and unweighted graphs.


 
Prerequisite: Terminology and Representations of Graphs
 

In this post we will implement graph using its Adjacency List representation without using any container provided by standard library.

As we already know that adjacency list associates each vertex in the graph with the collection of its neighboring vertices or edges i.e every vertex stores a list of adjacent vertices. There are many variations of adjacency list representation depending upon the implementation. 

Directed graph

For example, below is adjacency list representation of above graph –

Adjacency list

Above representation allows the storage of additional data on the vertices but practically very efficient when the graph contains only few edges. We will use STL vectors to implement Adjacency List representation of a graph.
 

1. Directed Graph implementation using STL –

 

Download   Run Code

Output:

0 –> 1
1 –> 2
2 –> 0 1
3 –> 2
4 –> 5
5 –> 4

 

 

2. Weighted Directed Graph implementation using STL –

 
We know that in a weighted graph, every edge will have a weight or cost associated with it as shown below:

  Weighted directed graph

Below is C++ implementation of a weighted directed graph using STL. The implementation is similar to above implementation of unweighted directed graph, except here we’ll also store the weight of every edge in the adjacency list.

 

Download   Run Code

Output:

(0, 1, 6)
(1, 2, 7)
(2, 0, 5) (2, 1, 4)
(3, 2, 10)
(4, 5, 1)
(5, 4, 3)

 

Note – We will follow above STL representation of graph as standard for all graph-related problems.

 
See more:

1. Graph Implementation in C++ without using STL

2. Graph Implementation in C

3. Graph Implementation in Java using Collections

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Somil
Guest
Somil

nice work

Pete
Guest
Pete

simple and concise

Abhishek
Guest
Abhishek

#define N 6
What if there are 7 vertices? What if there are 1002 vertices? Is it a good practice to fix the value of N beforehand?

One of the reasons I prefer techiedelight is because of it’s high-quality solutions which is lacking in other websites. For instance, the code will run despite theconst& in line number 39, but it’s good coding practice. However, I don’t think fixing the values beforehand is good at all. Please correct me if I am wrong

wpDiscuz