: you can watch a video on Graph Representation in C++ : Update here A graph is formally defined as a set of vertices and a set of edges connecting the vertices: V E 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 , i.e., if the number of odd-degree nodes is exactly 0 or 2. This is known as the problem. Eulerian Seven Bridges of Königsberg 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. In this method, and can each be represented using either of these STL containers: . V E 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 Now, the graph can be defined as a class and easily initialized using STL's : uniform initialization : Graph( :: < > &v, :: < ::pair< , >> &e) : v_(v), e_(e) {} ; ; :: < > v_; :: < ::pair< , >> e_; }; { :: < > v = { , , , }; :: < ::pair< , >> e = {{ , }, { , }, { , }, { , }, { , }, { , }, { , }}; ; :: << g.IsEulerWalkable() << :: ; } { class Graph public std vector int std vector std int int bool IsEulerWalkable () void PrintGraph () std vector int std vector std int int int main () std vector int 0 1 2 3 std vector std int int 1 3 1 3 3 0 3 0 0 2 2 1 2 3 Graph g (v, e) std cout std endl Notice how nicely initializing vertices and edges in the above code matches the input graph definition. Having the above definition and initialization, we can now implement as: IsEulerWalkable() Graph::IsEulerWalkable() { :: < > degrees(v_.size()); ( e : e_) { degrees[e.first]++; degrees[e.second]++; } countOdds = ; ( d : degrees) { (d % == ) { countOdds++; } } (countOdds == || countOdds == ); } bool // Create a table to hold degree of each vertex std vector int // Iterate all edges for auto int 0 // Iterate through degree table and count the number of odd ones for auto if 2 1 return 0 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 and , conceptually we represent the graph as a mapping between vertices and sets of adjacent vertices. Consider the following graph: V E This mapping can be represented using the table below: To model this in C++, we can create a new class called , which has two member variables: Vertex : an integer variable vertex_number : a set of adjacent vertices adjacents Vertex( v, :: < > a) : vertex_number(v), adjacents(a) {} vertex_number; :: < > adjacents; }; : Graph( :: <Vertex> v) : v_(v) {} ; :: <Vertex> v_; }; { ; :: << g.IsEulerWalkable() << :: ; } { struct Vertex int std set int int std set int { class Graph public std vector bool IsEulerWalkable () std vector int main () Graph g ({Vertex( , { , , }), Vertex( , { , , }), Vertex( , { , , }), Vertex( , { , , })}) 0 1 2 3 1 0 2 3 2 0 1 3 3 0 1 2 std cout std endl Again, notice how we used uniform initialization to initialize the graph to the input table that represents it. Having the above definition, we can rewrite as: IsEulerWalkable() Graph::IsEulerWalkable() { :: < > degrees(v_.size()); ( v : v_) { degrees[v.vertex_number] = v.adjacents.size(); } countOdds = ; ( d : degrees) { (d % == ) { countOdds++; } } (countOdds == || countOdds == ); } bool // Create a table to hold degree of each vertex std vector int // Iterate vertices for auto // Iterate through degree table and count the number of odd ones int 0 for auto if 2 1 return 0 2 Notice how we used STL's function to get the degree of each node: size() Using adjacency list, the degree of each node is already available. Method 3: Adjacency Matrix Adjacency matrix is a two-dimensional matrix where the entry is if there is an edge between vertices and . i,j 1 i j If the graph is undirected, the adjacency matrix is symmetrical: if entry is , then entry , is also . i, j 1 j i 1 The adjacency matrix can be represented using a two-dimensional matrix: : Graph( :: < :: < >> &adjacency) : adjacency_(adjacency) {} ; ; :: < :: < >> adjacency_; }; { :: < :: < >> adjacency = {{ , , , , }, { , , , , }, { , , , , }, { , , , , }, { , , , , }}; ; :: << << g.IsEulerWalkable() << :: ; ; } { class Graph public std vector std vector int bool IsEulerWalkable () void PrintGraph () std vector std vector int int main () std vector std vector int 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(): " std endl return 0 Again notice how nicely the initialization of the adjacency matrix using uniform initialization matches the given table. With the above class definition, we can rewrite as: IsEulerWalkable() Graph::IsEulerWalkable() { :: < > degrees(adjacency_.size()); ( i = ; i < adjacency_.size(); i++) { ( j = ; j < adjacency_.size(); j++) { (adjacency_[i][j] == ) { degrees[i]++; } } } countOdds = ; ( d : degrees) { (d % == ) { countOdds++; } } (countOdds == || countOdds == ); } bool // Create a table to hold degree of each vertex std vector int // Iterate all edges for int 0 for int 0 if 1 int 0 // Iterate through degree table and count the number of odd ones for auto if 2 1 return 0 2 Notice that to get the degree of each vertex, we have to iterate each row and add the number of . 1's The main concern with the adjacency matrix is its size. For a graph of vertices, we need entries. The advantage, however is that we can check if nodes i and j are adjacent just by checking entry , in time. n n^2 i j O(1) Comparison of the three methods How do these methods compare? The following table summarizes the main differences: The first method, direct translation, seems to have low memory size, but finding adjacents of a vertex takes , where m is the number of edges. O(m) The adjacency list improves the runtime complexity for finding adjacents of a vertex. However, if we just want to check if nodes are adjacent, the runtime is still not constant. i, j 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. Trade-off between std::vector, std::set, and std::list: As I mentioned in the beginning there is some trade-off 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) std::list: A list is not sorted Find in set takes O(n) Insert/Delete in set takes O(1) 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 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 find multigraph: A is similar to a graph, but it can have multiple edges between two nodes. multigraph A set or unordered_set cannot have repeated items. For example, in the multigraph shown in the above picture, we would have two similar edges between 0 and 1: and . This cannot be represented using a set. Therefore for representing a multigraph, you may want to use std::vector, list, or a . (0,1) (0,1) 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. Check my other video on Bazel & Visual Studio Code with GTest, Glog and Abseil:
