Graph Representation with Implementation in C++

Things to be discussed

• Introduction
• Different Types of Graph Representation

Fig: Simple Graph ( No self-loop and no Parallel Edges )

Introduction:
Graph representation is a method of representing the relationship between Vertices and Edges. This representation is required for efficient problem-solving.
The graph is represented as G(V, E) where V-vertices and E-edges.

Different Types of Graph Representation
There are four different types of graph representation method, below we will be exploring all different types of representation in detail.

• Adjacency Matrix
• Incidence Matrix
• Adjacency List
• Edge List

Adjacency Matrix:

• The easiest way to represent a graph
• It is an NxN matrix whose ij-th entry is the number of edges joining vertex i and j. For Simple Graph number of edges joining vertex, i and j are almost 1 as in simple graph we don't have Parallel Edges and Self-loop.
• Example:

• The Adjacency Matrix for the above graph is

• 0 - Means that there is no relation between u and v. ( For example (2,1) is 0 means from node 2 one can't reach 1)
• 1 - This means that there is a relation between u and v.
• This can be simply implemented using 2D Array.
• int adj_matrix[N][N]
• If the graph (simple)  is weighted then adjacency matrix representation can be extended so that the matrix contains the weights of the edge if the edge exists.
• Queries to check whether there is an edge between uv can be done in O(1).
• Space Required = O(V^2)
• Costly in space required in the Sparse Graph (Graph which is not fully connected).

The above graph we will be using as an example for Adjacency List and Edge List representation.

Here N=5, M=4 and edges are (1,2), (1,3), (2,4) and (2,5).

Incidence Matrix:

• It is the NxM matrix whose ij-th entry is 1 if vertex i is incident to the edge j and 0 otherwise. Here N is the number of vertices and M is the number of Edges.
• The Implementation is the same as that of Adjacency Matrix
• This is not so useful.

Adjacency List:

• In the adjacency list representation, each node in the graph is assigned and adjacency list that consists of nodes to which there is an edge from x.
• The adjacency list is the most popular way to represent graphs and most algorithms can be efficiently implemented using them.
• A convenient way to store the adjacency lists is to declare an array of vectors as follows for the non-weighted graph.
• vector<int> adj[N]
• For the weighted graph.
• vector< pair< int, int > > adj[N]
• The benefit of using the adjacency list is that we can efficiently find the nodes to which we can move from the given node through an edge.
• Queries to check whether there is an edge between uv and be done in O(E).
• Space required: O(V+E) is always in the worst case it would be equal to O(V^2)
• Implementation in C++

Edge List:

• An edge list contains all the edges of a graph in some order.
• This is a convenient way to represent a graph if the algorithm processes all edges of the graph and it is not needed to find edges that start at a given node.
• The edge list can be stored in a vector as
• vector< pair< int, int> > edges.
• For the weighted graph, we can store in the vector of pairs of pairs as
• vector< pair<int,  pair< int, int > > edges
• Also, a tuple can be used here like this
• vector< tuple<int, int, int> > edges
• Queries to check whether there is an edge between uv and be done in O(E).
• Space required: O(E) is always.
• Implementation in C++

Practice Problems

1. One more wired Game( OMWG )
2. Love Triangle's ( 939A )

3. New year transportation ( 500A )
4. Network Topology ( 292B )
5. A way to Home

Bonus Problem: Forming Teams ( 216B ) (Contributed by Ahmed Essam)

Note: Some problems may no require the above concept and some may require more concepts, these are warm-up problems, an easy one.

That's all for this article, in the next article we will be discussing Graph Traversal. Before moving to the next session do practice the above problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you ).

If you have some content OR material related to this then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by Learn DSA