Scribd
Upload
132 views

Adjacency Matrix

There are different ways to represent graphs on a computer. One common method is to use an adjacency matrix, which stores the connections between vertices in a graph as a 2D array. Each row and column represents a vertex, and a 1 in the matrix indicates an edge between those two vertices, while a 0 indicates no edge. Adjacency matrices allow constant-time access to edges and easy addition/removal of edges, but take more space than other methods for sparse graphs with few edges.

Uploaded by

Minahel Noor Fatima
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
132 views

Adjacency Matrix

There are different ways to represent graphs on a computer. One common method is to use an adjacency matrix, which stores the connections between vertices in a graph as a 2D array. Each row and column represents a vertex, and a 1 in the matrix indicates an edge between those two vertices, while a 0 indicates no edge. Adjacency matrices allow constant-time access to edges and easy addition/removal of edges, but take more space than other methods for sparse graphs with few edges.

Uploaded by

Minahel Noor Fatima
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

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.

You might also like