Graph Representations
In graph theory, a graph representation is a technique to store graph into
the memory of computer.
To represent a graph, we just need the set of vertices, and for each vertex
the neighbors of the vertex (vertices which is directly connected to it by an
edge). If it is a weighted graph, then the weight will be associated with each
edge.
There are different ways to optimally represent a graph, depending on the
density of its edges, type of operations to be performed and ease of use.
1. Adjacency Matrix
An adjacency matrix is a square matrix of N x N size where N is the
number of nodes in the graph and it is used to represent the connections
between the edges of a graph.
The adjacency matrix, also called the connection matrix, is a matrix
containing rows and columns which is used to represent a simple
labelled graph, with 0 or 1 in the position of (Vi , Vj) according to the
condition whether Vi and Vj are adjacent or not. It is a compact way to
represent the finite graph containing n vertices of a m x m matrix M.
Sometimes adjacency matrix is also called as vertex.
If the simple graph has no self-loops, Then the vertex matrix should
have 0s in the diagonal. It is symmetric for the undirected graph. The
connection matrix is considered as a square array where each row
represents the out-nodes of a graph and each column represents the
in-nodes of a graph. Entry 1 represents that there is an edge between
two nodes.
An adjacency matrix is a way of representing a graph as a matrix of
boolean (0’s and 1’s).
Let’s assume there are n vertices in the graph So, create a 2D
matrix adjMat[n][n] having dimension n x n.
If there is an edge from vertex i to j, mark adjMat[i][j] as 1.
If there is no edge from vertex i to j, mark adjMat[i][j] as 0.
Adjacency matrix is a sequential representation.
It is used to represent which nodes are adjacent to each other. i.e.
is there any edge connecting nodes to a graph.
Advantages of using Adjacency Matrix:
An adjacency matrix is simple and easy to understand.
Adding or removing edges from a graph is quick and easy.
It allows constant time access to any edge in the graph.
Undirected graph representation
Directed graph represenation
In the above examples, 1 represents an edge from row vertex to
column vertex, and 0 represents no edge from row vertex to
column vertex.
Undirected weighted graph represenation
Self loop :
Characteristics of the adjacency matrix are:
The size of the matrix is determined by the number of vertices in the
graph.
The number of nodes in the graph determines the size of the matrix.
The number of edges in the graph is simply calculated.
If the graph has few edges, the matrix will be sparse.
Applications of the Adjacency Matrix:
i. Graph algorithms: Many graph algorithms like Dijkstra’s
algorithm, Floyd-Warshall algorithm, and Kruskal’s algorithm use
adjacency matrices to represent graphs.
ii. Image processing: Adjacency matrices are used in image processing
to represent the adjacency relationship between pixels in an image.
iii. Finding the shortest path between two nodes: By performing
matrix multiplication on the adjacency matrix, one can find the
shortest path between any two nodes in a graph.
