June 1st 2020
A graph is formally defined as a set of vertices V and a set of edges E connecting the vertices:
G=(V,E)
Each edge is a pair of vertices. For a directed graph, the edges are ordered pairs and for undirected graphs, the edges are unordered.
How do we represent a graph in C++? This article summarizes various options available using C++ Standard Template Library (STL).
Method 1: Direct Translation of the Definition: G=(V,E)
This is probably the most straightforward method of representing a graph in C++: we only translate the math definition directly to STL containers.
std::vector, std::set, std::list
.
Consider this simple graph:
For simplicity, out of all available options, let’s pick:
 V: std::vector
 E: std::vector
 Edges: std::pair
class Graph {
public:
Graph(std::vector<int> &v, std::vector<std::pair<int, int>> &e)
: v_(v), e_(e) {}
bool IsEulerWalkable();
void PrintGraph();
std::vector<int> v_;
std::vector<std::pair<int, int>> e_;
};
int main() {
std::vector<int> v = {0, 1, 2, 3};
std::vector<std::pair<int, int>> e = {{1, 3}, {1, 3}, {3, 0}, {3, 0},
{0, 2}, {2, 1}, {2, 3}};
Graph g(v, e);
std::cout << g.IsEulerWalkable() << std::endl;
}
Notice how nicely initializing vertices and edges in the above code matches the input graph definition.
IsEulerWalkable()
as:
bool Graph::IsEulerWalkable() {
// Create a table to hold degree of each vertex
std::vector<int> degrees(v_.size());
// Iterate all edges
for (auto e : e_) {
degrees[e.first]++;
degrees[e.second]++;
}
int countOdds = 0;
// Iterate through degree table and count the number of odd ones
for (auto d : degrees) {
if (d % 2 == 1) {
countOdds++;
}
}
return (countOdds == 0  countOdds == 2);
}
The above code is very self explanatory: we iterate through all edges and add to the degree of each vertex that is on the edge. In the end, we count the number of vertices with odd edges and return true if the count was 0 or 2.
Method 2: Adjacency List
In this method rather than having two separate sets for V and E, conceptually we represent the graph as a mapping between vertices and sets of adjacent vertices. Consider the following graph:
This mapping can be represented using the table below:
Vertex
, which has two member variables:

vertex_number
: an integer variable

adjacents
: a set of adjacent vertices
struct Vertex {
Vertex(int v, std::set<int> a) : vertex_number(v), adjacents(a) {}
int vertex_number;
std::set<int> adjacents;
};
class Graph {
public:
Graph(std::vector<Vertex> v) : v_(v) {}
bool IsEulerWalkable();
std::vector<Vertex> v_;
};
int main() {
Graph g({Vertex(0, {1, 2, 3}), Vertex(1, {0, 2, 3}), Vertex(2, {0, 1, 3}),
Vertex(3, {0, 1, 2})});
std::cout << g.IsEulerWalkable() << std::endl;
}
Again, notice how we used uniform initialization to initialize the graph to the input table that represents it.
IsEulerWalkable()
as:
bool Graph::IsEulerWalkable() {
// Create a table to hold degree of each vertex
std::vector<int> degrees(v_.size());
// Iterate vertices
for (auto v : v_) {
degrees[v.vertex_number] = v.adjacents.size();
}
// Iterate through degree table and count the number of odd ones
int countOdds = 0;
for (auto d : degrees) {
if (d % 2 == 1) {
countOdds++;
}
}
return (countOdds == 0  countOdds == 2);
}
size()
function to get the degree of each node:
Using adjacency list, the degree of each node is already available.
Method 3: Adjacency Matrix
Adjacency matrix is a twodimensional matrix where the entry i,j is 1 if there is an edge between vertices i and j.
If the graph is undirected, the adjacency matrix is symmetrical: if entry i, j is 1, then entry j, i is also 1.
The adjacency matrix can be represented using a twodimensional matrix:
class Graph {
public:
Graph(std::vector<std::vector<int>> &adjacency) : adjacency_(adjacency) {}
bool IsEulerWalkable();
void PrintGraph();
std::vector<std::vector<int>> adjacency_;
};
int main() {
std::vector<std::vector<int>> adjacency = {{0, 1, 1, 0, 0},
{1, 0, 1, 1, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 0, 1},
{0, 1, 0, 1, 0}};
Graph g(adjacency);
std::cout << "g.isEulerWalkable(): " << g.IsEulerWalkable() << std::endl;
return 0;
}
Again notice how nicely the initialization of the adjacency matrix using uniform initialization matches the given table.
IsEulerWalkable()
as:
bool Graph::IsEulerWalkable() {
// Create a table to hold degree of each vertex
std::vector<int> degrees(adjacency_.size());
// Iterate all edges
for (int i = 0; i < adjacency_.size(); i++) {
for (int j = 0; j < adjacency_.size(); j++) {
if (adjacency_[i][j] == 1) {
degrees[i]++;
}
}
}
int countOdds = 0;
// Iterate through degree table and count the number of odd ones
for (auto d : degrees) {
if (d % 2 == 1) {
countOdds++;
}
}
return (countOdds == 0  countOdds == 2);
}
1's
.
n
vertices, we need
n^2
entries. The advantage, however is that we can check if nodes i and j are adjacent just by checking entry i, j in
O(1)
time.
Comparison of the three methods
How do these methods compare? The following table summarizes the main differences:
O(m)
, where m is the number of edges.
The adjacency list improves the runtime complexity for finding adjacents of a vertex. However, if we just want to check if nodes i, j are adjacent, the runtime is still not constant.
Adjacency matrix has the highest space, but due to the nature of vector’s access time, you can quickly check to see if two nodes are adjacent in constant time.
Tradeoff between std::vector, std::set, and std::list:
As I mentioned in the beginning there is some tradeoff between using STL’s vector, set, or list to represent the vertices and the edges.
Let’s review some main differences:
std::set:
 A set is automatically sorted
 Insert/Delete/Find in set takes O(log n)
std::unordered_set:
 An unordered set is not sorted
 Insert/Delete/Find in set takes O(log 1)
std::vector:
 A vector is not sorted
 Insert/Delete/Find in set takes O(n)
 A list is not sorted
 Find in set takes O(n)
 Insert/Delete in set takes O(1)
std::list:
Based on this, if you want to keep your edges or vertices sorted, you should probably go with a set. If you want a very fast search time, you should go with an unordered_set.
If find time is not that important, you can go with a list or a vector. But there is one more important reason that one might use a vector/list instead of set, which is representing multigraph:
A multigraph is similar to a graph, but it can have multiple edges between two nodes.
(0,1)
and
(0,1)
. This cannot be represented using a set. Therefore for representing a multigraph, you may want to use std::vector, list, or a
multiset
.
Summary
We showed how you can represent a graph in C++ using one of the three methods: direct translation of the graph definition, adjacency list, and adjacency matrix. If you are preparing for technical job interviews, make sure you understand the difference and the pros and cons for each method.