# Adjacency Matrix For Graphs

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.

**Table of contents**

**Adjacency Matrix****How to create an adjacency matrix?**-
**Creating Adjacency matrix for Undirected graph** -
**Creating Adjacency matrix for the Directed graph** **Algorithm**

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

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

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.

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"); }}

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:

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 |

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