Adjacency Matrix Representation in Data Structure

In the world of data structures and algorithms, graphs are one of the most powerful and widely used non-linear data structures. From modeling real-world networks like social media connections, road maps, and airline routes to solving complex problems in computer science, graphs play a crucial role.

But to use graphs effectively in programs or algorithms, we first need a way to represent them in memory. That’s where graph representation techniques come into play — and one of the most common among them is the Adjacency Matrix.

An adjacency matrix offers a clean, systematic, and easy-to-understand way to represent the relationship between nodes (also called vertices) using a two-dimensional array. It is especially useful in dense graphs where the number of edges is large.

What is an Adjacency Matrix?

An Adjacency Matrix is a 2D array (or matrix) used to represent a graph. Each row and column of the matrix represents a vertex, and the entries of the matrix indicate whether a pair of vertices are connected by an edge.

Matrix Definition:

If G is a graph with n vertices, then the adjacency matrix is an n x n matrix adj[][] such that:

• adj[i][j] = 1 if there is an edge from vertex i to vertex j
• adj[i][j] = 0 if there is no edge between vertex i and vertex j

For weighted graphs, adj[i][j] = weight instead of just 1.

Understanding the Key Concepts of Adjacency Matrix

Example 1: Adjacency Matrix for Unweighted Graph

Suppose we have a graph with 4 vertices:
Edges: (0–1), (0–2), (1–2), (2–3)

Matrix

     0  1  2  3
  ------------
0 | 0  1  1  0
1 | 1  0  1  0
2 | 1  1  0  1
3 | 0  0  1  0

• It is undirected, so the matrix is symmetric.
• adj[0][1] = 1 means there is an edge between vertex 0 and 1.

Example 2: Adjacency Matrix for Weighted Directed Graph

Let’s say:

• Edge(0 → 1, weight = 5)
• Edge(0 → 3, weight = 10)
• Edge(1 → 2, weight = 3)

Matrix

     0   1   2   3
  ----------------
0 |  0   5   0  10
1 |  0   0   3   0
2 |  0   0   0   0
3 |  0   0   0   0

C Program: Adjacency Matrix

#include <stdio.h>

#define MAX_VERTICES 10

void displayMatrix(int adj[MAX_VERTICES][MAX_VERTICES], int vertices);

int main() {
    int adj[MAX_VERTICES][MAX_VERTICES];
    int vertices, edges;
    int i, j, src, dest;

    printf("Enter the number of vertices (max %d): ", MAX_VERTICES);
    scanf("%d", &vertices);

    // Check for valid number of vertices
    if (vertices <= 0 || vertices > MAX_VERTICES) {
        printf("Error: Number of vertices must be between 1 and %d.\n", MAX_VERTICES);
        return 1;
    }

    // Initialize the adjacency matrix with 0
    for (i = 0; i < vertices; i++) {
        for (j = 0; j < vertices; j++) {
            adj[i][j] = 0;
        }
    }

    printf("Enter the number of edges: ");
    scanf("%d", &edges);

    printf("Enter each edge in the format: source destination (0 to %d)\n", vertices - 1);

    for (i = 0; i < edges; i++) {
        printf("Edge %d: ", i + 1);
        scanf("%d%d", &src, &dest);

        // Input validation
        if (src < 0 || src >= vertices || dest < 0 || dest >= vertices) {
            printf("❌ Invalid edge (%d, %d). Vertex index should be between 0 and %d. Skipping...\n", src, dest, vertices - 1);
            continue;
        }

        // Undirected graph — add both ways
        adj[src][dest] = 1;
        adj[dest][src] = 1;
    }

    // Display final matrix
    displayMatrix(adj, vertices);

    return 0;
}

void displayMatrix(int adj[MAX_VERTICES][MAX_VERTICES], int vertices) {
    int i, j;
    printf("\n✅ Adjacency Matrix Representation:\n\n");

    // Print column headers
    printf("   ");
    for (i = 0; i < vertices; i++) {
        printf("%d ", i);
    }
    printf("\n");

    for (i = 0; i < vertices; i++) {
        printf("%d: ", i);
        for (j = 0; j < vertices; j++) {
            printf("%d ", adj[i][j]);
        }
        printf("\n");
    }
}

Output

Enter the number of vertices (max 10): 4
Enter the number of edges: 4
Enter each edge in the format: source destination (0 to 3)
Edge 1: 1
3
Edge 2: 0
2
Edge 3: 3
1
Edge 4: 2
3

✅ Adjacency Matrix Representation:

   0 1 2 3 
0: 0 0 1 0 
1: 0 0 0 1 
2: 1 0 0 1 
3: 0 1 1 0 

Java Program: Adjacency Matrix

public class AdjacencyMatrix {
    public static void main(String[] args) {
        int vertices = 4;
        int[][] adjMatrix = new int[vertices][vertices];

        // adding edges
        adjMatrix[0][1] = 1;
        adjMatrix[0][2] = 1;
        adjMatrix[1][2] = 1;
        adjMatrix[2][3] = 1;

        System.out.println("Adjacency Matrix:");
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                System.out.print(adjMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Output

Adjacency Matrix:
0 1 1 0 
0 0 1 0 
0 0 0 1 
0 0 0 0

Advantages and Disadvantages of Adjacency Matrix

Advantages

Disadvantages

Adjacency Matrix vs Adjacency List

✅ Use Matrix when: Number of edges ≈ Number of vertices²
✅ Use List when: Number of edges ≪ Number of vertices²

Read Full Article here: Adjacency Matrix vs Adjacency List

Real-World Applications

• Routing Tables in Networking
• Flight Routes (airports as nodes, flights as edges)
• Game Maps (like chessboard or maze traversal)
• Social Networks (friendship as edges)
• Compiler Design (dependency graphs)

FAQs – Adjacency Matrix Representation

Q1. Is adjacency matrix good for sparse graphs?

No, because it consumes a lot of memory with mostly 0s. Adjacency List is better for sparse graphs.

Q2. Can adjacency matrix represent both directed and undirected graphs?

Yes, it can represent both. For directed graphs, matrix is not symmetric.

Q3. What is the space complexity of an adjacency matrix?

Always O(V²), regardless of how many edges are in the graph.

Q4. Is adjacency matrix useful in Dijkstra’s algorithm?

It can be used but adjacency lists are preferred due to better performance with sparse graphs.

Summary of Adjacency Matrix

Final Words

The Adjacency Matrix is a foundational graph representation method. It offers fast edge lookup and simplicity, making it ideal for dense graphs or when quick access to edges is needed. However, for sparse graphs or memory-constrained applications, you may prefer adjacency lists.