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 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
representation of an undirected and directed graph is given below:

### 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 graphs
is very simple to implement.
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.

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 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
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;
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;
Category: DSA Tutorials A crazy computer and programming lover. He spend most of his time in programming, blogging and helping other programming geeks.

## 4 thoughts on “Representation of Graphs: Adjacency Matrix and Adjacency List”

1. Yifang

I’d like to have an example on reading adj matrix for graph.

2. Firoz Iqbal

Easy for learning

3. Hind

thank you for this wonderfull tutorial.
please I need to generate this matrix of adjacency but for a degree of 0.5 (all possible cases), how can I do that please, for a specific integer N

4. shankar

nice ,it helps me 🙂