Graph Representation in C++

Summary: I explain how a graph can be represented in C++ using variousSTL containers and what are the pros and cons for each method. This is intended for people who are studying for technical job interviews.

Update: you can watch a video on Graph Representation in C++ here:

What is a Graph Again?

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

For each method, we will implement a simple algorithm to check to see if the graph is Eulerian, i.e., if the number of odd-degree nodes is exactly 0 or 2. This is known as the Seven Bridges of Königsberg problem.

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…