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