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

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

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.

Output:

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:

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.

Output:

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

See more:

(2 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
kpeTeHo3aBbp

Hi there! First of all nice job on the whole site, it covers a lot of topics and I find it pretty useful for refreshing my algo and data structure skills.

I do have one remark though about these particular solutions – they seem to be introducing memory leaks for nodes whose adjacency list contains more than one vertex. In this particular input, that is node with index 2 (and value 2). The node describing the outgoing edge {2,1} is not freed, thus resulting in a memory leak. I think that this small tweak of the Graph destructor should fix the issue:

// Destructor
~Graph() {
for (int i = 0; i next;
while (next != nullptr) {
Node * tmp = next->next;
delete next;
next = tmp;
}
}

}

Please let me know if I’m missing something. Keep up the good work!

Guest
kpeTeHo3aBbp

```// Destructor ~Graph() { for (int i = 0; i < N; i++) { Node * next = head[i]->next; while (next != nullptr) { Node * tmp = next->next; delete next; next = tmp; } delete[] head[i]; }```

``` ```

``` delete[] head; }```

Guest

How do we add an edge to an existing graph??