Trusted answers to developer questions

What is an adjacency matrix?

Free System Design Interview Course

Many candidates are rejected or down-leveled due to poor performance in their System Design Interview. Stand out in System Design Interviews and get hired in 2024 with this popular free course.

An adjacency matrix is a two-dimensional matrix used to map the association between the nodes of a graph. A graph is a set of vertices (nodes) connected by edges.

In an adjacency matrix, 0 means that no association between nodes exists and 1 means that an association between nodes does exist.

svg viewer

Code

In the example below, we have implemented the adjacency matrix for the above illustration.

In a two-dimensional matrix, rows and columns are initialized with index 0 and so on. That’s why we have subtracted 1 from each index below.

#include <iostream>
using namespace std;
int main() {
int adjMatrix[5][5];
// intializing adjMatrix to zero
for(int i = 0; i < 5 ; i++){
for(int j = 0; j < 5; j++){
adjMatrix[i][j] = 0;
}
}
// setting node 1
adjMatrix[1-1][2-1] = 1;
adjMatrix[1-1][3-1] = 1;
// setting node 2
adjMatrix[2-1][1-1] = 1;
adjMatrix[2-1][5-1] = 1;
// setting node 3
adjMatrix[3-1][1-1] = 1;
adjMatrix[3-1][4-1] = 1;
// setting node 4
adjMatrix[4-1][3-1] = 1;
adjMatrix[4-1][5-1] = 1;
// setting node 5
adjMatrix[5-1][2-1] = 1;
adjMatrix[5-1][4-1] = 1;
// printing
for(int i = 0; i < 5 ; i++){
for(int j = 0; j < 5; j++){
cout<< adjMatrix[i][j]<< " ";
}
cout<<"\n";
}
return 0;
}

RELATED TAGS

matrix
adjacency
basics
graphs
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?