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.

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.

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

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

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=

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.

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

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.

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

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:

Example

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

Adjacency Matrix for the weighted graph:

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

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

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