 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;

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

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

2. Easy for learning

3. 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. nice ,it helps me 🙂