Adjacency Matrix

Representation of a graph using a 2D matrix where each cell indicates the presence of an edge between vertices

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

Visualization of 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;
}
}

# adjacencymatrixforundirectedunweighted.py
# Read number of vertices and edges
vertex, edges = map(int, input().split())

# Initialize adjacency matrix with False
adj_mat = [[False for _ in range(vertex)] for _ in range(vertex)]

# Read edges and populate matrix
for _ in range(edges):
u, v = map(int, input().split())
adj_mat[u][v] = True
adj_mat[v][u] = True  # For undirected graph

# Print the adjacency matrix
for i in range(vertex):
for j in range(vertex):
    print(1 if adj_mat[i][j] else 0, end=" ")
print()

# Example usage:
# Input: 5 6
#        0 1
#        0 2  
#        0 3
#        2 3
#        3 4
# Output: 0 1 1 1 0
#         1 0 0 0 0
#         1 0 0 1 0
#         1 0 1 0 1
#         0 0 0 1 0

// adjacencymatrixforundirectedunweighted.js
// Read input (assuming input is provided via readline or similar)
function createUndirectedUnweightedMatrix(vertex, edges, edgeList) {
// Initialize adjacency matrix with false
const adjMat = Array(vertex).fill(null).map(() => Array(vertex).fill(false));

// Add edges to matrix
for (const [u, v] of edgeList) {
    adjMat[u][v] = true;
    adjMat[v][u] = true; // For undirected graph
}

// Print the adjacency matrix
for (let i = 0; i < vertex; i++) {
    let row = "";
    for (let j = 0; j < vertex; j++) {
        row += (adjMat[i][j] ? 1 : 0) + " ";
    }
    console.log(row);
}

return adjMat;
}

// Example usage:
const vertex = 5;
const edges = 6;
const edgeList = [[0,1], [0,2], [0,3], [2,3], [3,4]];
createUndirectedUnweightedMatrix(vertex, edges, edgeList);

// Output: 0 1 1 1 0
//         1 0 0 0 0
//         1 0 0 1 0
//         1 0 1 0 1
//         0 0 0 1 0

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

Visualization of 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;
}
}

# adjacencymatrixforundirectedweighted.py
import sys

# Read number of vertices and edges
vertex, edges = map(int, input().split())

# Initialize adjacency matrix with infinity
INF = float('inf')
adj_mat = [[INF for _ in range(vertex)] for _ in range(vertex)]

# Read edges with weights and populate matrix
for _ in range(edges):
u, v, weight = map(int, input().split())
adj_mat[u][v] = weight
adj_mat[v][u] = weight  # For undirected graph

# Set diagonal elements to 0 (distance from vertex to itself)
for i in range(vertex):
adj_mat[i][i] = 0

# Print the adjacency matrix
for i in range(vertex):
for j in range(vertex):
    if adj_mat[i][j] == INF:
        print("INF", end=" ")
    else:
        print(adj_mat[i][j], end=" ")
print()

# Example usage:
# Input: 4 5
#        0 1 2
#        0 2 4
#        1 2 1
#        1 3 5
#        2 3 3
# Output: 0 2 4 INF
#         2 0 1 5
#         4 1 0 3
#         INF 5 3 0

// adjacencymatrixforundirectedweighted.js
function createUndirectedWeightedMatrix(vertex, edges, edgeList) {
const INF = Number.MAX_SAFE_INTEGER;

// Initialize adjacency matrix with infinity
const adjMat = Array(vertex).fill(null).map(() => Array(vertex).fill(INF));

// Add weighted edges to matrix
for (const [u, v, weight] of edgeList) {
    adjMat[u][v] = weight;
    adjMat[v][u] = weight; // For undirected graph
}

// Set diagonal elements to 0
for (let i = 0; i < vertex; i++) {
    adjMat[i][i] = 0;
}

// Print the adjacency matrix
for (let i = 0; i < vertex; i++) {
    let row = "";
    for (let j = 0; j < vertex; j++) {
        if (adjMat[i][j] === INF) {
            row += "INF ";
        } else {
            row += adjMat[i][j] + " ";
        }
    }
    console.log(row);
}

return adjMat;
}

// Example usage:
const vertex = 4;
const edges = 5;
const edgeList = [[0,1,2], [0,2,4], [1,2,1], [1,3,5], [2,3,3]];
createUndirectedWeightedMatrix(vertex, edges, edgeList);

// Output: 0 2 4 INF
//         2 0 1 5
//         4 1 0 3
//         INF 5 3 0

3. Adjacency Matrix for Directed Unweighted Graph

Visualization of 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;
}
}

# adjacencymatrixfordirectedunweighted.py
# Read number of vertices and edges
vertex, edges = map(int, input().split())

# Initialize adjacency matrix with False
adj_mat = [[False for _ in range(vertex)] for _ in range(vertex)]

# Read directed edges and populate matrix
for _ in range(edges):
u, v = map(int, input().split())
adj_mat[u][v] = True  # Only set one direction for directed graph

# Print the adjacency matrix
for i in range(vertex):
for j in range(vertex):
    print(1 if adj_mat[i][j] else 0, end=" ")
print()

# Example usage:
# Input: 4 5
#        0 1
#        0 2
#        1 3
#        2 1
#        3 2
# Output: 0 1 1 0
#         0 0 0 1
#         0 1 0 0
#         0 0 1 0

// adjacencymatrixfordirectedunweighted.js
function createDirectedUnweightedMatrix(vertex, edges, edgeList) {
// Initialize adjacency matrix with false
const adjMat = Array(vertex).fill(null).map(() => Array(vertex).fill(false));

// Add directed edges to matrix
for (const [u, v] of edgeList) {
    adjMat[u][v] = true;  // Only set one direction for directed graph
}

// Print the adjacency matrix
for (let i = 0; i < vertex; i++) {
    let row = "";
    for (let j = 0; j < vertex; j++) {
        row += (adjMat[i][j] ? 1 : 0) + " ";
    }
    console.log(row);
}

return adjMat;
}

// Example usage:
const vertex = 4;
const edges = 5;
const edgeList = [[0,1], [0,2], [1,3], [2,1], [3,2]];
createDirectedUnweightedMatrix(vertex, edges, edgeList);

// Output: 0 1 1 0
//         0 0 0 1
//         0 1 0 0
//         0 0 1 0

4. Adjacency Matrix for Directed Weighted Graph

Visualization of 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;
}
}

# adjacencymatrixfordirectedweighted.py
import sys

# Read number of vertices and edges
vertex, edges = map(int, input().split())

# Initialize adjacency matrix with infinity
INF = float('inf')
adj_mat = [[INF for _ in range(vertex)] for _ in range(vertex)]

# Read directed edges with weights and populate matrix
for _ in range(edges):
u, v, weight = map(int, input().split())
adj_mat[u][v] = weight  # Only set one direction for directed graph

# Set diagonal elements to 0 (distance from vertex to itself)
for i in range(vertex):
adj_mat[i][i] = 0

# Print the adjacency matrix
for i in range(vertex):
for j in range(vertex):
    if adj_mat[i][j] == INF:
        print("INF", end=" ")
    else:
        print(adj_mat[i][j], end=" ")
print()

# Example usage:
# Input: 4 5
#        0 1 2
#        0 2 4
#        1 3 5
#        2 1 1
#        3 2 3
# Output: 0 2 4 INF
#         INF 0 INF 5
#         INF 1 0 INF
#         INF INF 3 0

// adjacencymatrixfordirectedweighted.js
function createDirectedWeightedMatrix(vertex, edges, edgeList) {
const INF = Number.MAX_SAFE_INTEGER;

// Initialize adjacency matrix with infinity
const adjMat = Array(vertex).fill(null).map(() => Array(vertex).fill(INF));

// Add directed weighted edges to matrix
for (const [u, v, weight] of edgeList) {
    adjMat[u][v] = weight;  // Only set one direction for directed graph
}

// Set diagonal elements to 0
for (let i = 0; i < vertex; i++) {
    adjMat[i][i] = 0;
}

// Print the adjacency matrix
for (let i = 0; i < vertex; i++) {
    let row = "";
    for (let j = 0; j < vertex; j++) {
        if (adjMat[i][j] === INF) {
            row += "INF ";
        } else {
            row += adjMat[i][j] + " ";
        }
    }
    console.log(row);
}

return adjMat;
}

// Example usage:
const vertex = 4;
const edges = 5;
const edgeList = [[0,1,2], [0,2,4], [1,3,5], [2,1,1], [3,2,3]];
createDirectedWeightedMatrix(vertex, edges, edgeList);

// Output: 0 2 4 INF
//         INF 0 INF 5
//         INF 1 0 INF
//         INF INF 3 0

Adjacency Matrix

On this page