Adjacency List vs Matrix When to Choose Which in DSA C - Compare & Choose

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, 0-2, and 1-2 in a graph with 3 nodes?

DSA C

int graph[3][3] = {0};
graph[0][1] = 1;
graph[1][0] = 1;
graph[0][2] = 1;
graph[2][0] = 1;
graph[1][2] = 1;
graph[2][1] = 1;
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        printf("%d ", graph[i][j]);
    }
    printf("\n");
}

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

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

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

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

💡 Hint

Think about how edges are represented in a matrix for an undirected graph.

The adjacency matrix uses 1 to mark edges between nodes. Since edges are undirected, the matrix is symmetric. The edges 0-1, 0-2, and 1-2 set those positions to 1.

🧠 Conceptual

intermediate

Choosing adjacency list for sparse graphs

Why is an adjacency list preferred over an adjacency matrix for a graph with many nodes but very few edges?

A Because adjacency lists use less memory by storing only existing edges.

B Because adjacency lists require a fixed size regardless of edges.

C Because adjacency matrices are faster to traverse for sparse graphs.

D Because adjacency matrices cannot represent sparse graphs.

💡 Hint

Think about memory usage when most possible edges do not exist.

Adjacency lists store only the edges that exist, saving memory when edges are few compared to possible connections.

❓ Predict Output

advanced

Output of adjacency list after adding edges

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

DSA C

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int dest;
    struct Node* next;
} Node;

Node* createNode(int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

int main() {
    Node* graph[3] = {NULL, NULL, NULL};
    // Add edge 0->1
    Node* node1 = createNode(1);
    node1->next = graph[0];
    graph[0] = node1;
    // Add edge 0->2
    Node* node2 = createNode(2);
    node2->next = graph[0];
    graph[0] = node2;
    // Add edge 1->2
    Node* node3 = createNode(2);
    node3->next = graph[1];
    graph[1] = node3;
    // Print adjacency list
    for (int i = 0; i < 3; i++) {
        printf("%d: ", i);
        Node* temp = graph[i];
        while (temp) {
            printf("%d -> ", temp->dest);
            temp = temp->next;
        }
        printf("NULL\n");
    }
    return 0;
}

A

0: 1 -> 2 -> NULL
1: 2 -> NULL
2: NULL

B

0: NULL
1: NULL
2: NULL

C

0: 1 -> NULL
1: 2 -> NULL
2: NULL

D

0: 2 -> 1 -> NULL
1: 2 -> NULL
2: NULL

💡 Hint

New nodes are added at the head of the list, so the last added edge appears first.

Edges are added at the front, so for node 0, edge to 2 is printed before edge to 1. Node 1 has edge to 2. Node 2 has no edges.

🧠 Conceptual

advanced

When adjacency matrix is better than adjacency list

In which scenario is an adjacency matrix a better choice than an adjacency list?

A When the graph has very few edges and memory is limited.

B When the graph is dense and quick edge lookup is needed.

C When edges need to be stored with variable weights efficiently.

D When the graph is very large and sparse.

💡 Hint

Think about speed of checking if an edge exists between two nodes.

Adjacency matrices allow constant time edge lookup, which is useful in dense graphs where many edges exist.

🚀 Application

expert

Memory usage comparison for large sparse graph

Consider a graph with 10,000 nodes and 15,000 edges. Which data structure uses less memory and why?

A Adjacency list uses less memory because it stores only existing edges.

B Adjacency matrix uses less memory because it uses a fixed size array.

C Both use the same memory because they represent the same graph.

D Adjacency matrix uses less memory because it stores edges as bits.

💡 Hint

Think about how many entries adjacency matrix stores versus adjacency list.

Adjacency matrix stores 10,000 x 10,000 = 100 million entries, mostly zeros, while adjacency list stores only 15,000 edges, saving memory.