Adjacency Matrix Representation in DSA C

Mental Model

We use a square grid to show which nodes connect to which nodes. Each cell tells if there is a direct link between two points.

Analogy: Imagine a city map with intersections as points and roads as connections. The grid is like a table where each row and column is an intersection, and a mark means a road connects them.

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 1 0]

Dry Run Walkthrough

Input: Graph with 3 nodes: edges between 0-1 and 1-2

Goal: Show the adjacency matrix that marks connections between nodes

Step 1: Initialize a 3x3 matrix with all zeros

   0 1 2
0 [0 0 0]
1 [0 0 0]
2 [0 0 0]

Why: Start with no connections marked

Step 2: Mark connection from node 0 to node 1

   0 1 2
0 [0 1 0]
1 [0 0 0]
2 [0 0 0]

Why: Node 0 connects to node 1

Step 3: Mark connection from node 1 to node 0

   0 1 2
0 [0 1 0]
1 [1 0 0]
2 [0 0 0]

Why: Node 1 connects back to node 0 (undirected graph)

Step 4: Mark connection from node 1 to node 2

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 0 0]

Why: Node 1 connects to node 2

Step 5: Mark connection from node 2 to node 1

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 1 0]

Why: Node 2 connects back to node 1 (undirected graph)

Result:

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 1 0]

Annotated Code

DSA C

#include <stdio.h>
#define N 3

void printMatrix(int matrix[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int adjMatrix[N][N] = {0};

    // Mark edge 0-1
    adjMatrix[0][1] = 1; // mark connection from node 0 to 1
    adjMatrix[1][0] = 1; // mark connection from node 1 to 0

    // Mark edge 1-2
    adjMatrix[1][2] = 1; // mark connection from node 1 to 2
    adjMatrix[2][1] = 1; // mark connection from node 2 to 1

    printMatrix(adjMatrix);
    return 0;
}

adjMatrix[0][1] = 1; // mark connection from node 0 to 1

mark edge from node 0 to node 1

adjMatrix[1][0] = 1; // mark connection from node 1 to 0

mark edge from node 1 to node 0 for undirected graph

adjMatrix[1][2] = 1; // mark connection from node 1 to 2

mark edge from node 1 to node 2

adjMatrix[2][1] = 1; // mark connection from node 2 to 1

mark edge from node 2 to node 1 for undirected graph

Output

0 1 0 

1 0 1 

0 1 0 

Complexity Analysis

Time: O(N^2) because we create and print an N by N matrix

Space: O(N^2) because the matrix stores connection info for every pair of nodes

vs Alternative: Compared to adjacency lists, adjacency matrix uses more space but allows quick check if two nodes are connected

Edge Cases

Empty graph with zero nodes

Matrix is empty, no connections to mark

DSA C

int adjMatrix[N][N] = {0};

Graph with no edges

Matrix remains all zeros, showing no connections

DSA C

int adjMatrix[N][N] = {0};

Self loop edge (node connected to itself)

Matrix cell at [node][node] is set to 1

DSA C

adjMatrix[node][node] = 1;

When to Use This Pattern

When you need to quickly check if two nodes are connected and the graph size is small or dense, use adjacency matrix representation.

Common Mistakes

Mistake: Forgetting to mark both directions in an undirected graph
Fix: Always set both adjMatrix[i][j] and adjMatrix[j][i] to 1 for undirected edges

Mistake: Using wrong indices causing out-of-bounds errors
Fix: Ensure node indices are within 0 to N-1 before marking matrix

Summary

It shows graph connections using a 2D grid where each cell marks if two nodes connect.

Use it when you want fast connection checks and the graph is not too large.

The key is that each row and column represent nodes, and the cell shows if they link.