Data Structure (2130702)

Representation of Graph

• A diagrammatic representation of a graph may have limited usefulness. However such a representation is not feasible when number of nodes an edges in a graph is large.
• Hence the graph can be represented in another two ways.
  • Matrix representation of Graph
  • Linked List representation of Graph

Matrix Representation of Graph (Adjacency matrix)

• It is easy to store and manipulate matrices and hence the graphs represented by them in the computer.
• Let G = (V, E) be a simple diagraph in which V = {V₁, V₂,…., V_n} and the nodes are assumed to be ordered from V₁ to V_n.
• An n x n matrix A is called Adjacency matrix of the graph G whose elements are a_ij are given by.

  $a_{ij} = \left\{\begin{array}{ll}1& if(V_i,V_j)\in E\\ 0& otherwise\end{array}\right.$

• An element of the adjacency matrix is either 0 or 1
• Any matrix whose elements are either 0 or 1 is called bit matrix or Boolean matrix
• For a given graph G = m(V, E), an adjacency matrix depends upon the ordering of the elements of V
• For different ordering of the elements of V we get different adjacency matrices.

• The number of elements in the i_th row whose value is 1 is equal to the out-degree of node V_i.
• The number of elements in the j_th column whose value is 1 is equal to the in-degree of node V_j.
• For a NULL graph which consist of only n nodes but no edges, the adjacency matrix has all its elements 0. i.e. the adjacency matrix is the NULL matrix.

Linked List representation of Graph (Adjacency List Representation)