Implementing Graph Data Structure in C++ Using STL

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.