In this post, we will be implementing Graph Data Structure in C++. As a language, C++ provides a lot of STLs (or Standard Template Libraries) that make life easy when implementing advanced data structure. We will be using STL to implement a Graph.

In case you want to know more about Graphs, please refer to this post where we talk about the general principles behind Graph Data Structures.

## 1 – The Graph Data Structure Class

We will be using a vector of vectors to denote the Graph as an adjacency list. Here is a the Graph class that can solve our purpose:

class Graph { public: //Vector of Vectors vector<vector<int>> adjList; //Graph Constructor Graph(vector<edge> const &edges, int N){ adjList.resize(N); for (auto &edge: edges) { //insert at the end adjList[edge.src].push_back(edge.dest); } } };

As you can see, here we declare a vector of vectors known as **adjList**. Also, we have defined a constructor that accepts a vector of type **edge** and the number of nodes in a graph N.

It traverses through the vector of **edges **and pushes the link between the source and destination to the adjacency list. Below is the **edge** structure.

struct edge { int src, dest; };

This structure only has two integer members for the **source **and **destination **nodes.

## 2 – Driver Method

Once the Graph class is done, we can fill information in the graph and also print the contents of the graph using a utility function.

int main() { vector<edge> edges = { { 0, 1 }, { 1, 3 }, { 2, 1 }, { 3, 2 }, { 3, 4 }, { 4, 0 }, { 4, 1 }, {4, 3} }; // Number of nodes in the graph int N = 5; // construct graph Graph graph(edges, N); // print adjacency list representation of graph printGraph(graph, N); return 0; }

Here, we are simply defining a **vector **with the **edges **information and then we instantiate an object of the **Graph **class using the constructor. In the constructor, we pass the **edges **information and also the number of **nodes **in the graph.

Finally, we print the **Graph**.

Below is the utility **print **function.

void printGraph(Graph const &graph, int N) { for (int i = 0; i < N; i++) { // print current vertex number cout << i << " --> "; // print all neighboring vertices of vertex i for (int v : graph.adjList[i]) cout << v << " "; cout << endl; } }

Below is the output of the **print **function.

```
0 --> 1
1 --> 3
2 --> 1
3 --> 2 4
4 --> 0 1 3
```

## Conclusion

With this, we have looked at **implementing graph data structure** in C++ using STL such as a vector.

## 0 Comments