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…