Adjacency Matrix

A 2D matrix representing a graph

Introduction

An Adjacency matrix is a representation of a graph using a 2D matrix, where the rows and columns correspond to the vertices (nodes) of the graph. The value in the matrix indicates whether a pair of vertices is connected by an edge. It is often represented using Boolean values: 0 indicates no connection, and 1 indicates the presence of an edge between the vertices.

1. Adjacency Matrix for Undirected Unweighted Graph

Each cell in the adjacency matrix, denoted as A[i][j], shows whether there is an edge between vertex i and vertex j.

  • If there is no edge, A[i][j] = 0.
  • If there is an edge from i to j, A[i][j] = A[j][i] = 1.

Coding Implementation

//adjacencymatrixforundirectedunweighted.cpp
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int vertex, edges;
cin >> vertex >> edges;
vector<vector<bool>> adjMat(vertex, vector<bool>(vertex, 0));
int u, v;
for (int i = 0; i < edges; i++)
{
    cin >> u >> v;
    adjMat[u][v] = 1;
    adjMat[v][u] = 1;
}
for (int i = 0; i < vertex; i++)
{
    for (int j = 0; j < vertex; j++)
    {
        cout << adjMat[i][j] << " ";
    }
    cout << endl;
}
}

Explanation

  • A[0][1] = 1 because there is an edge between vertex 0 and 1.
  • A[0][2] = 1 because there is an edge between vertex 0 and 2.
  • A[0][3] = 1 because there is an edge between vertex 0 and 3.
  • A[1][0] = 1 because there is an edge between vertex 1 and 0.
  • A[2][0] = 1 because there is an edge between vertex 2 and 0.
  • A[2][3] = 1 because there is an edge between vertex 2 and 3.
  • A[3][0] = 1 because there is an edge between vertex 3 and 0.
  • A[3][2] = 1 because there is an edge between vertex 3 and 2.
  • A[3][4] = 1 because there is an edge between vertex 3 and 4.
  • A[4][3] = 1 because there is an edge between vertex 4 and 3.

All other cells A[i][j] = 0 where no edge exists.

In Undirected graphs, the matrix is symmetric, meaning A[i][j] = A[j][i], because an edge from i to j also implies an edge from j to i.

2. Adjacency Matrix for Undirected Weighted Graph

Each cell in the adjacency matrix, denoted as A[i][j], shows whether there is an edge between vertex i and vertex j.

  • If there is no edge, A[i][j] = INFINITE.
  • If there is an edge from i to j, A[i][j] = A[j][i] = whaving weight w.

Coding Implementation

//adjacencymatrixforundirectedweighted.cpp
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int vertex, edges;
cin >> vertex >> edges;
vector<vector<int>> adjMat(vertex, vector<int>(vertex, INT_MAX));
int u, v, weight;
for (int i = 0; i < edges; i++)
{
    cin >> u >> v >> weight;
    adjMat[u][v] = weight;
    adjMat[v][u] = weight;
}
for (int i = 0; i < vertex; i++)
{
    adjMat[i][i] = 0;
}
for (int i = 0; i < vertex; i++)
{
    for (int j = 0; j < vertex; j++)
    {
        if (adjMat[i][j] == INT_MAX)
            cout << "INF" << " ";
        else
            cout << adjMat[i][j] << " ";
    }
    cout << endl;
}
}

3. Adjacency Matrix for Directed Unweighted Graph

Each cell in the adjacency matrix, denoted as A[i][j], shows whether there is an edge between vertex i and vertex j

  • If there is no edge from vertex i to vertex j, then A[i][j] = INFINITE.

  • If there is a directed edge from vertex i to vertex j, then A[i][j] = 1.

Coding Implementation

//adjacencymatrixfordirectedunweighted.cpp
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int vertex, edges;
cin >> vertex >> edges;
vector<vector<bool>> adjMat(vertex, vector<bool>(vertex,0));
int u, v;
for (int i = 0; i < edges; i++)
{
    cin >> u >> v;
    adjMat[u][v] = 1;
}
for (int i = 0; i < vertex; i++)
{
    for (int j = 0; j < vertex; j++)
    {
        cout << adjMat[i][j] << " ";
    }
    cout << endl;
}
}

4. Adjacency Matrix for Directed Weighted Graph

Each cell in the adjacency matrix, denoted as A[i][j], shows whether there is an edge between vertex i and vertex j.

  • If there is no edge from vertex i to vertex j, A[i][j] = INFINITE.
  • If there is a directed edge from vertex i to vertex j, A[i][j] = w, w is the weight of that edge.

Coding Implementation

//adjacencymatrixfordirectedweighted.cpp
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int vertex, edges;
cin >> vertex >> edges;
vector<vector<int>> adjMat(vertex, vector<int>(vertex, INT_MAX));
int u, v, weight;
for (int i = 0; i < edges; i++)
{
    cin >> u >> v >> weight;
    adjMat[u][v] = weight;
}
for (int i = 0; i < vertex; i++)
{
    adjMat[i][i] = 0;
}
for (int i = 0; i < vertex; i++)
{
    for (int j = 0; j < vertex; j++)
    {
        if (adjMat[i][j] == INT_MAX)
            cout << "INF" << " ";
        else
            cout << adjMat[i][j] << " ";
    }
    cout << endl;
}
}