Graph Representation

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++

That's all for this article, in the next article we will be discussing Graph Traversal. Before proceeding to the next session do solve the problem set Question.

If you find any error in this article then please feel free to comment.
Thank You for Reading.
Enjoy!


Comments