Adjacency Matrix Representation in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency matrix after adding edges

What is the printed adjacency matrix after adding edges between nodes 0-1, 1-2, and 2-0 in a graph with 3 nodes?

DSA C

#include <stdio.h>
#define N 3

int main() {
    int adj[N][N] = {0};
    adj[0][1] = 1;
    adj[1][2] = 1;
    adj[2][0] = 1;

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

A [[0,1,0],[0,0,1],[1,0,0]]

B [[0,1,0],[1,0,1],[1,0,0]]

C [[0,1,0],[0,0,1],[0,0,0]]

D [[0,1,1],[0,0,1],[1,0,0]]

💡 Hint

Check which pairs have 1s in the matrix based on edges added.

Edges added are 0->1, 1->2, and 2->0. So adj[0][1], adj[1][2], and adj[2][0] are 1. Others remain 0.

❓ Predict Output

intermediate

Output after removing an edge in adjacency matrix

Given a 4-node graph with edges 0-1, 1-2, 2-3, and 3-0, what is the adjacency matrix after removing the edge 1-2?

DSA C

#include <stdio.h>
#define N 4

int main() {
    int adj[N][N] = {0};
    adj[0][1] = 1;
    adj[1][2] = 1;
    adj[2][3] = 1;
    adj[3][0] = 1;

    adj[1][2] = 0; // remove edge

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

A [[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]]

B [[0,1,0,0],[0,0,0,0],[0,0,0,1],[1,0,0,0]]

C [[0,1,0,0],[0,0,0,1],[0,0,0,1],[1,0,0,0]]

D [[0,1,0,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]]

💡 Hint

Look carefully at the row for node 1 after removal.

Edge 1->2 is removed, so adj[1][2] is 0. Other edges remain.

🔧 Debug

advanced

Identify the error in adjacency matrix initialization

What error will this code produce when compiling or running?

DSA C

#include <stdio.h>
#define N 3

int main() {
    int adj[N][N];
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            adj[i][j] = 0;
        }
    }
    return 0;
}

A Runs without error and initializes matrix

B Compilation error: array index out of bounds

C Runtime error: segmentation fault due to out-of-bounds access

D Logical error: matrix not fully initialized

💡 Hint

Check the loop conditions and array size carefully.

Loops use <= N which goes beyond valid indices 0 to N-1, causing out-of-bounds access at runtime.

🧠 Conceptual

advanced

Memory usage of adjacency matrix vs adjacency list

Which statement correctly compares memory usage of adjacency matrix and adjacency list for a graph with V vertices and E edges?

A Adjacency matrix always uses less memory than adjacency list

B Adjacency list uses O(V^2) memory, adjacency matrix uses O(V+E)

C Both use the same memory regardless of edges

D Adjacency matrix uses O(V^2) memory, adjacency list uses O(V+E)

💡 Hint

Think about how adjacency matrix stores all possible edges.

Adjacency matrix stores all V*V entries, so O(V^2). Adjacency list stores only existing edges plus vertices, so O(V+E).

❓ Predict Output

expert

Output of adjacency matrix after symmetric edge insertion

What is the adjacency matrix output after inserting edges to make an undirected graph with edges between nodes 0-1, 1-2, and 2-0 in a 3-node graph?

DSA C

#include <stdio.h>
#define N 3

int main() {
    int adj[N][N] = {0};
    int edges[3][2] = {{0,1}, {1,2}, {2,0}};

    for (int i = 0; i < 3; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        adj[u][v] = 1;
        adj[v][u] = 1;
    }

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

A [[0,1,1],[1,0,1],[1,1,0]]

B [[0,1,0],[1,0,1],[1,0,0]]

C [[0,1,1],[0,0,1],[1,1,0]]

D [[0,0,1],[1,0,1],[1,1,0]]

💡 Hint

Undirected edges mean symmetric entries in the matrix.

Each edge u-v sets adj[u][v] and adj[v][u] to 1, making the matrix symmetric.

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