Representation of Graphs: Adjacency Matrix and Adjacency List

Adjacency Matrix

A graph G = (V, E) where v= {0, 1, 2, . . .
n-1} can be represented using two dimensional integer array of size n x n.
int adj[20][20] can be used to store a
graph with 20 vertices
adj[i][j] = 1, indicates presence of edge
between two vertices i and j.
adj[i][j] = 0, indicates absence of edge
between two vertices i and j.
  • A graph is represented using square matrix.
  • Adjacency matrix of an undirected graph is
    always a symmetric matrix, i.e. an edge (i, j) implies the edge (j, i).
  • Adjacency matrix of a directed graph is
    never symmetric, adj[i][j] = 1 indicates a directed edge from vertex i to
    vertex j.

Read Previous Article: Graphs: Introduction and Terminology
An example of adjacency matrix
representation of an undirected and directed graph is given below:
Adjacency Matrix Representation of Undirected Graph

Adjacency Matrix Representation of Directed Graph

Adjacency matrix representation of a
weighted graph

For weighted graph, the matrix adj[ ][ ] is
represented as:
If there is an edge between vertices i and
j then adj[i][j] = weight of the edge (i, j) otherwise adj[i][j] = 0.
An example of representation of weighted
graph is given below:
Adjacency Matrix Representation of Weighted Graph
  • Adjacency matrix representation of graphs
    is very simple to implement.
  • Memory requirement: Adjacency matrix
    representation of a graph wastes lot of memory space. Such matrices are found
    to be very sparse. This representation requires space for n2 elements
    for a graph with n vertices. If the graph has e number of edges then n2 –
    e elements in the matrix will be 0.
  • Presence of an edge between two vertices Vi
    and Vj can be checked in constant time. if(adj[i][j] == 1) then edge is present between vertices i and j, else edge is absent between vertices i and j
  • Degree of a vertex can easily be calculated
    by counting all non-zero entries in the corresponding row of the adjacency
    matrix.

Adjacency List

A graph can also be represented using alinked list. For each vertex, a list of adjacent vertices is maintained using a
linked list. It creates a separate linked list for each vertex Vi in
the graph G = (V, E).
Adjacency list of a graph with n nodes can
be represented by an array of pointers. Each pointer points to a linked list of
the corresponding vertex. Below figure shows the adjacency list representation
of a graph.
Adjacency List Representation of Graph
  • Adjacency list representation of a graph is
    very memory efficient when the graph has a large number of vertices but very
    few edges.
  • For an undirected graph with n vertices and
    e edges, total number of nodes will be n + 2e. If e is large then due to
    overhead of maintaining pointers, adjacency list representation does not remain
    cost effective over adjacency matrix representation of a graph.
  • Degree of a node in an undirected graph is
    given by the length of the corresponding linked list.
  • Finding indegree of a directed graph
    represented using adjacency list will require O (e) comparisons. Lists pointed
    by all vertices must be examined to find the indegree of a node in a directed
    graph.
  • Checking the existence of an edge between
    two vertices i and j is also time consuming. Linked list of vertex i must be
    searched for the vertex j.

A graph can be represented using a
structure as defined below:
#define MAX 30              //graph has maximum of 30 nodes
typedef struct node
{
               struct
node *next;
               int
vertex;
}node;
node *head[MAX];
If a weighted graph is to be represented
using a adjacency list, then structure “node” should be modified to include the
weight of an edge. Thus the definition of ‘struct node’ is
modified as below:
typedef struct node
{
struct node
*next;
               int
vertex;
               int
weight;

}node;

2 thoughts on “Representation of Graphs: Adjacency Matrix and Adjacency List

Leave a Reply

Your email address will not be published. Required fields are marked *