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.