Adjacency Matrix For Graphs

Adjacency Matrix For Graphs

4 mins read1K Views Comment
Updated on Apr 12, 2024 10:55 IST

The adjacency matrix also called the connection matrix, is a matrix containing rows and columns which is used to represent a simple labelled graph. In this article, we will study the Adjacency Matrix for different types of graphs.

adjacency matrix

An Adjacency Matrix is a method of representing graphs in matrix form. The adjacency matrix plays a vital role in describing finite graphs, making them easier to understand and compact representation. A graph is a collection of nodes and edges. In an adjacency matrix, nodes and edges of the graph are used to describe the graph. The nodes are the graph’s vertices, whereas the edges are the finite set of ordered pairs. In this article, we will discuss the Adjacency Matrix For Graphs, the representation of the adjacency matrix, How to create an adjacency matrix from the graph, and the adjacency matrix for both undirected and directed graphs. 

Table of contents

Adjacency Matrix

An adjacency matrix is simply a square matrix or connection matrix used to describe a finite graph in matrix format. It maps the connection between the edges and vertices of the graph in a two-dimensional matrix. 

If a graph is of n vertices or nodes, its corresponding adjacency matrix would be n x n size. Each matrix entry indicates the number of matrices from one vertex to another. It represents a weighted graph in matrix format as adj [x][y] = w, meaning there is an edge from vertex x to vertex y with a weight of w. 

B Tree in Data Structure
B Tree in Data Structure
A B-tree is a self-balancing data structure ideal for managing large data volumes. It ensures fast search, insert, and delete operations by keeping elements sorted and tree height minimal. B-trees...read more
ArrayList vs. LinkedList
ArrayList vs. LinkedList
ArrayList and LinkedList are linear data structure and are part of collection framework present in java.util packages. In this article, we will briefly discuss the difference between ArrayList and LinkedList...read more
Difference between Stack and Queue
Difference between Stack and Queue
This article compares stacks and queues in programming. Stacks use LIFO to undo mechanisms and function calls, while queues use FIFO to manage processes, such as printing jobs or CPU...read more

Also explore: Data Structures and Algorithms Online Courses & Certifications.

Also read: Queue Data Structure: Types, Implementation, Applications

Adjacency matrix representation

If there is an undirected graph G that has n vertices, then the adjacency matrix A will be of n x n size, and if there is an entry in the matrix A = a[i]j], it will be defined as-

 if there exists a path from vertex i to vertex j, 

              a[i][j] = 1          

else                      

              a[i][j] = 0 

Some important points:

  • If a path exists from vertex i to vertex j, then the entry at a[i][j] will be 1.
  • If there is no path from vertex i to vertex j, the entry at a[i][j] will be 0.
  • If all the diagonal entries of the matrix are 0, then the graph has no self-loops.
  • If the value of the ith row and jth column is equal to the jth row and ith column, then the adjacency matrix is symmetric for the respective graph.

Also Read: Implementing ArrayList in Java

Also Read: ArrayList in Java

How to create an adjacency matrix?

After knowing what the adjacency matrix is and its representation, let’s learn how to create an adjacency matrix from a given graph. 

Assume a graph G with n number of a vertex. Then the corresponding adjacency matrix is represented as

 A=

a11 a12 a13 ….. a1n
a21 a22 a23 ….. a2n
a31 a32 a33 …. a3n
:: :: :: :: ::
an1 an2 an3 ….. ann

Creating Adjacency matrix for Undirected graph

In an undirected graph, edges do not have any directions, so the edge is assumed to be bi-directional. If there is an edge connecting nodes A and B, it is assumed that the data can be transferred from A to B and B to A. 

Consider the following undirected graph, and we will design the corresponding adjacency matrix for that graph.

2022_10_image-58.jpg

The undirected graph has seven vertices, then the matrix will have a total of 7 x 7 entries, and the corresponding adjacency matrix for the above undirected will be as 

i↓    j→ A B C D E F G
A 0 1 0 1 0 0 1
B 1 0 1 0 0 1 0
C 0 1 0 1 1 0 0
D 1 0 1 0 1 0 0
E 0 0 1 1 0 1 1
F 0 1 0 0 1 0 0
G 1 0 0 0 1 0 1

Creating Adjacency matrix for Directed graph

In a directed graph, edges are associated with the directions. Consider the following directed graph and design an adjacency matrix for the corresponding graph.

2022_10_image-59.jpg

The directed graph has six vertices, so there will be 6 x 6 entries in the adjacency matrix. 

i↓    j→ A B C D E F
A 0 1 0 0 0 1
B 0 0 1 0 0 0
C 0 0 0 1 0 0
D 1 0 0 0 1 0
E 0 0 0 0 0 0
F 0 0 0 1 1 0

Algorithm


 
int main() {
int adjMatrix[V][V];
init(adjMat);
addEdge(adjMat, 0, 1);
addEdge(adjMat, 0, 3);
addEdge(adjMat, 2, 1);
addEdge(adjMat, 2, 3);
addEdge(adjMat, 3, 1);
printMatrix(adjMat);
return 0;
}
#include <stdio.h>
#define V 4
void init(int arr[][V]) {
int i, j;
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
arr[i][j] = 0;
}
void addEdge(int arr[][V], int i, int j) {
arr[i][j] = 1;
arr[j][i] = 1;
}
void printMatrix(int arr[][V]) {
int i, j;
for (i = 0; i < V; i++) {
printf("%d: ", i);
for (j = 0; j < V; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
}
Copy code

Illustration of the above code:

2022_10_image-62.jpg

Example

2022_10_image-63.jpg

Consider a weighted directed graph, and design an adjacency matrix for that graph. 

Adjacency Matrix for the weighted graph:

i↓    j→ A B C D E F
A 0 3 0 0 0 1
B 0 0 2 0 0 0
C 0 0 0 4 0 0
D 5 3 0 0 4 0
E 0 0 3 0 0 0
F 0 0 0 8 6 0

 

All About Skew Symmetric Matrix
All About Skew Symmetric Matrix
A skew-symmetric matrix is a square matrix whose transpose is equal to its negative. In other words, it is a matrix that satisfies the condition A^T = -A. This type...read more

All about Symmetric Matrix
All about Symmetric Matrix
A matrix is a rectangular arrangement of numbers (real or complex) or symbols arranged in rows and columns. The number in the matrix are called the elements, and if the...read more

Matrix Multiplication in C
Matrix Multiplication in C
A matrix is a collection of numbers organized in rows and columns. Matrices can be manipulated using operations like Addition, Subtraction, and Multiplication. Multiplying two matrices is only possible when...read more

Types of Matrix
Types of Matrix
In Linear Algebra, Matrices are one of the most important topics of mathematics. The application of matrix is not just limited to mathematical solving problems; it has its applications across...read more

Adjacency Matrix For Graphs
Adjacency Matrix For Graphs
An Adjacency Matrix is a method of representing graphs in matrix form. The adjacency matrix plays a vital role in describing finite graphs, making them easier to understand and compact...read more

Lower Triangular Matrix: Definition, Example, and Properties
Lower Triangular Matrix: Definition, Example, and Properties
Discover the essentials of lower triangular matrices in linear algebra. Explore their unique properties, practical applications in solving linear systems, and their significance in mathematical computations. Perfect for students and...read more

Transpose of a Matrix
Transpose of a Matrix
Transpose of a matrix is a matrix flipped over its main diagonal, switching the matrix’s rows and column indices. In this article, we will briefly discuss what transpose of a...read more

Confusion Matrix in Machine Learning
Confusion Matrix in Machine Learning
Are you tired of your AI models getting confused? Untangle their mysteries with the Confusion Matrix, your secret weapon for accuracy! Decode True Positives, False Negatives, and more to uncover...read more

Diagonal Matrix: Definition, Example, and Properties
Diagonal Matrix: Definition, Example, and Properties
A diagonal matrix is a special type of square matrix in which all non-diagonal entries are equal to zero, but all diagonal entries can either be zero or non-zero. This...read more

Identity Matrix: Definition, Examples, and Properties
Identity Matrix: Definition, Examples, and Properties
A square matrix of order n x n with ones on the main diagonal and zeros elsewhere is known as an Identity Matrix. From solving a system of linear equations...read more

Why, How, and When to Adopt a Matrix Organizational Structure
Why, How, and When to Adopt a Matrix Organizational Structure
Discover the meaning, types, advantages and disadvantages of the matrix organizational structure. This article delves into its real-world applications, guiding you through adoption steps, potential pitfalls, and when it's best...read more

Matrix Multiplication: A Beginner’s Guide to Understand and Implement
Matrix Multiplication: A Beginner’s Guide to Understand and Implement
Matrix multiplication is a binary operation whose output is also a binary operation. If A and B are two matrices of order m x n and n x p, then the order of the output matrix will...read more

Upper Triangular Matrix: Definition, Example, and Properties
Upper Triangular Matrix: Definition, Example, and Properties
Explore the world of upper triangular matrices in our comprehensive guide. Understand their definition, properties, and practical applications in solving linear equations and beyond. Dive into the role of these...read more

How to Calculate the Determinant of a Matrix?
How to Calculate the Determinant of a Matrix?
The determinant of a matrix is a scalar value that is calculated from the elements of the Square matrix. It is used to determine whether a given matrix is invertible...read more
About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio