Adjacency Matrix Implementation in C++

We have covered Graph data structure in our previous post and in there, we have learned that graphs can be represented in two different ways, one is Adjacency Matrix and another is Adjacency List. In this post, we are going to learn about the Adjacency Matrix and its implementation for different types of graphs.

Adjacency Matrix.

An adjacency matrix is a way of representing a graph as a matrix of size n x n filled with 0s and 1s, where n is the number of vertices in the graph. The entry in the ith row and jth column of the matrix indicates whether there is an edge from vertex i to vertex j.

Adjacency Matrix implementation is different for directed and undirected graphs. Let's learn the implementation one by one.

Adjacency Matrix for Undirected Graph.

For a simple undirected graph, the matrix is symmetric around its diagonal, since the edges are bidirectional. It means if there is an edge between vertex A to vertex B then there must be an edge from vertex B to vertex A.

Note: The diagonal entries in the matrix are always 0 in an undirected graph since there are no self-loops. Also, the matrix is symmetric about its diagonal, so the entry in row i and column j is the same as the entry in row j and column i. (alert-passed)

Example:

Adjacency Matrix for Undirected Graph

Below is the C++ code implementation for the Adjacency matrix of an undirected graph.

//C++ code for printing adjacency matrix of undirected graph
#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
int adj_matrix[MAX_SIZE][MAX_SIZE];

int main() {
    // n: number of vertices, m: number of edges
    int n, m;
    cout<<"Enter number of vertices: ";
    cin >> n;
    cout<<"Enter number of edges: ";
    cin >> m;
    
    // initialize adjacency matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            adj_matrix[i][j] = 0;
        }
    }
    
    cout<< "Add edges to the graph:\n";
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // since the graph is undirected
        adj_matrix[u][v] = 1;
        adj_matrix[v][u] = 1;
    }
    
    // print adjacency matrix
    cout << "Adjacency matrix:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << adj_matrix[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Output:

Enter number of vertices: 4
Enter number of edges: 5
Add edges to the graph:
0 1
0 2
1 2
1 3
2 3
Adjacency matrix:
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

Adjacency Matrix for Directed Graph.

For a directed graph, the matrix is not necessarily symmetric, since the edges are not bidirectional.

Example:

Adjacency Matrix for Directed Graph

Below is the C++ code implementation for the Adjacency matrix of a directed graph.

//C++ code for printing adjacency matrix of directed graph
#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
int adj_matrix[MAX_SIZE][MAX_SIZE];

int main() {
    // n: number of vertices, m: number of edges
    int n, m;
    cout<<"Enter number of vertices: ";
    cin >> n;
    cout<<"Enter number of edges: ";
    cin >> m;
    
    // initialize adjacency matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            adj_matrix[i][j] = 0;
        }
    }
    
    cout<< "Add edges to the graph:\n";
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // since the graph is directed
        adj_matrix[u][v] = 1;
    }
    
    // print adjacency matrix
    cout << "Adjacency matrix:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << adj_matrix[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Output:

Enter number of vertices: 4
Enter number of edges: 5
Add edges to the graph:
0 1
0 2
1 2
2 3
3 1
Adjacency matrix:
0 1 1 0
0 0 1 0
0 0 0 1
0 1 0 0

Adjacency Matrix is a simple and efficient way to represent a dense graph but we have another method of representation like the Adjacency list when the graph is not dense.

Adjacency Matrix Implementation in C++