Graph Implementation in C++ (without using STL)

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


Prerequisite: Terminology and Representations of Graphs


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

The adjacency list representation of graph also allows the storage of additional data on the vertices but practically very efficient when the graph contains only few edges.


1. Directed Graph implementation in C++ –


Download   Run Code


0 — -> 1
1 — -> 2
2 — -> 1 -> 0
3 — -> 2
4 — -> 5
5 — -> 4



2. Weighted Directed Graph implementation in C++ –

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 directed weighted graph. The implementation is similar to above implementation of unweighted graph, except we’ll also store the weight of every edge in the adjacency list.


Download   Run Code


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


See more:

1. Graph Implementation in C

2. Graph Implementation in C++ using STL

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