Easiest implementation of Graph in cpp

Question

Currently I am learning graph implementation. I found 2 implementation namely matrix and adjacency list using vector in cpp. But the problems I face are following

With matrix

• Passing to function is hard
• Adding new nodes is not possible
• memory inefficient

Vector implementation of adjacency list

// Code taken from geeksforgeeks
vector<int> adj[V]; 

// adding edge from u to v
adj[u].push_back(v);

• adding new node is not possible
• and also passing to function is hard

So I want a solution in cpp which can solve above 2 problems.

Answer 1

I have efficient and easiest implementation of graph in cpp. It solves all problems you mentioned above. It is called as vector in vector.

// Suppose at start we have
// number of nodes
int nodes = 5;

// number of edges
int edges = 4;

// define graph
vector<vector<int>> graph(nodes, vector<int>());

int u, v; // edge from u -> v
for(int i=0;i<edges;i++){
    cin >> u >> v;
    graph[u].push_back(v);
}

// suppose we want to add node
graph.push_back(vector<int>());

// print graph content
int index = 0;
for(auto x : graph){
    cout << index << "-> ";
    for(auto y: x){
        cout << y << " ";
    }
    cout << endl;
    index ++;
}

Input to above code

5 4
0 1
0 2
2 1
2 3

Output

0-> 1 2 
1-> 
2-> 1 3 
3-> 
4-> 
5-> // new node

Advantages

• Can add node at run time
• memory efficient
• you can pass to function easily like normal vector
• you can find nodes in another function without passing it.