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.

Practice

1. What does an adjacency matrix represent in graph theory?

easy

A. A 2D array showing connections between nodes

B. A list of nodes in the graph

C. A sequence of edges in order

D. A tree structure of nodes

Solution

1. Step 1: Understand adjacency matrix concept

   An adjacency matrix is a 2D array where rows and columns represent nodes.

2. Step 2: Identify what the matrix stores

   Each cell shows if an edge exists between two nodes (1 for connected, 0 for not).

3. Final Answer:

   A 2D array showing connections between nodes -> Option A

4. Quick Check:

   Adjacency matrix = 2D array [OK]

Hint: Adjacency matrix is always a 2D grid of node connections [OK]

Common Mistakes:

• Confusing adjacency matrix with adjacency list
• Thinking it stores node values instead of edges
• Assuming it is a sequence or tree

2. Which of the following is the correct way to declare a 4x4 adjacency matrix in C?

easy

A. int matrix[4];

B. int matrix[4][4];

C. int matrix[];

D. int matrix[4,4];

Solution

1. Step 1: Recall C array declaration syntax

   In C, a 2D array is declared as type name[rows][columns].

2. Step 2: Match syntax for 4x4 matrix

   For 4 rows and 4 columns, it is int matrix[4][4];

3. Final Answer:

   int matrix[4][4]; -> Option B

4. Quick Check:

   2D array syntax = int matrix[4][4]; [OK]

Hint: Use int matrix[rows][columns] for 2D arrays in C [OK]

Common Mistakes:

• Using single dimension array for matrix
• Using comma inside brackets (invalid syntax)
• Not specifying both dimensions

3. Given the following adjacency matrix for a graph with 3 nodes:

int matrix[3][3] = {
  {0, 1, 0},
  {1, 0, 1},
  {0, 1, 0}
};

Which nodes are directly connected to node 1 (index 1)?

medium

A. [1, 2]

B. [0, 1]

C. [0, 2]

D. [2]

Solution

1. Step 1: Identify row for node 1

   Node 1 corresponds to index 1, so look at matrix[1]: {1, 0, 1}.

2. Step 2: Find indices with value 1

   Positions 0 and 2 have 1, meaning node 1 connects to nodes 0 and 2.

3. Final Answer:

   [0, 2] -> Option C

4. Quick Check:

   matrix[1][0] and matrix[1][2] = 1 [OK]

Hint: Check the row of the node for 1s to find connections [OK]

Common Mistakes:

• Confusing row and column indices
• Including the node itself as connected
• Reading zeros as connections

4. Consider this code snippet to initialize a 3x3 adjacency matrix in C:

int matrix[3][3];
for (int i = 0; i < 3; i++) {
  for (int j = 0; j < 3; j++) {
    matrix[i][j] = 0;
  }
}
matrix[1][3] = 1;

What is the error in this code?

medium

A. Accessing out-of-bounds index matrix[1][3]

B. Missing semicolon after for loop

C. Incorrect initialization of matrix elements

D. Using wrong data type for matrix

Solution

1. Step 1: Check loop ranges and matrix size

   Matrix is 3x3, so valid indices are 0 to 2 for both rows and columns.

2. Step 2: Identify invalid index usage

   matrix[1][3] tries to access column index 3, which is out of bounds.

3. Final Answer:

   Accessing out-of-bounds index matrix[1][3] -> Option A

4. Quick Check:

   Index 3 invalid for size 3 array [OK]

Hint: Array indices go from 0 to size-1; check carefully [OK]

Common Mistakes:

• Ignoring array bounds and using invalid indices
• Assuming loops fix out-of-range errors
• Confusing row and column indices

5. You have a directed graph with 4 nodes. The adjacency matrix is:

int matrix[4][4] = {
  {0, 1, 0, 0},
  {0, 0, 1, 0},
  {1, 0, 0, 0},
  {0, 0, 0, 0}
};

Which nodes have no incoming edges?

hard

A. [0]

B. [0, 3]

C. [1, 3]

D. [3]

Solution

1. Step 1: Understand incoming edges in adjacency matrix

   Incoming edges to a node are shown by 1s in that node's column.

2. Step 2: Check each column for 1s

   Column 0 has 1 at row 2 (node 2 -> node 0).
   Column 1 has 1 at row 0 (node 0 -> node 1).
   Column 2 has 1 at row 1 (node 1 -> node 2).
   Column 3 has no 1s (all 0s).

3. Step 3: Identify nodes with no incoming edges

   Nodes 1 and 3 have no incoming edges because column 1 has 1 at row 0 (so node 1 has incoming edge), so this is incorrect. Actually, column 1 has 1 at row 0, so node 1 has incoming edge. Column 3 has no 1s, so node 3 has no incoming edges. Node 0 has incoming edge from node 2. Node 2 has incoming edge from node 1. So only node 3 has no incoming edges.

4. Final Answer:

   [3] -> Option D

5. Quick Check:

   Column 3 all 0s [OK]

Hint: Look down columns to find incoming edges for each node [OK]

Common Mistakes:

• Checking rows instead of columns for incoming edges
• Confusing directed and undirected edges
• Missing edges from nodes to themselves