### 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.

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

graph with 20 vertices

adj[i][j] = 1, indicates presence of edge

between two vertices i and j.

between two vertices i and j.

adj[i][j] = 0, indicates absence of edge

between two vertices i and j.

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:

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:

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.

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:

graph is given below:

- 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).

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.

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

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:

structure as defined below:

#define MAX 30 //graph has maximum of 30 nodes

typedef struct node

{

struct

node *next;

node *next;

int

vertex;

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:

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;

*next;

int

vertex;

vertex;

int

weight;

weight;

}node;

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

Easy for learning