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.

Practice

1. Which data structure is generally better for representing a graph with very few edges compared to the number of vertices?

easy

A. Adjacency List

B. Adjacency Matrix

C. Edge List

D. Incidence Matrix

Solution

1. Step 1: Understand graph density

   A graph with very few edges compared to vertices is called a sparse graph.

2. Step 2: Choose efficient representation for sparse graphs

   Adjacency lists store only existing edges, saving space for sparse graphs, unlike adjacency matrices which use space for all possible edges.

3. Final Answer:

   Adjacency List -> Option A

4. Quick Check:

   Sparse graph = Adjacency List [OK]

Hint: Sparse graph? Use adjacency list for space efficiency [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs wastes space
• Confusing edge list with adjacency matrix
• Thinking adjacency matrix is always better

2. Which of the following is the correct way to declare an adjacency matrix for a graph with 4 vertices in C?

easy

A. int graph[4][4][4];

B. int graph[4];

C. int graph[][] = new int[4][4];

D. int graph[4][4];

Solution

1. Step 1: Recall C array declaration syntax

   In C, a 2D array for 4 vertices is declared as int graph[4][4];

2. Step 2: Check options for correctness

   int graph[4][4]; matches correct syntax; int graph[4]; is 1D array; int graph[][] = new int[4][4]; uses Java syntax; int graph[4][4][4]; is 3D array.

3. Final Answer:

   int graph[4][4]; -> Option D

4. Quick Check:

   C 2D array syntax = int graph[4][4]; [OK]

Hint: C 2D arrays use int name[rows][cols]; syntax [OK]

Common Mistakes:

• Using Java or other language syntax in C
• Declaring wrong array dimensions
• Confusing 1D and 2D arrays

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

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

What is the output of the code snippet that prints all neighbors of vertex 1?

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

medium

A. 0 2

B. 1 2

C. 0 1

D. 1 0 2

Solution

1. Step 1: Analyze adjacency matrix row for vertex 1

   Row 1 is {1, 0, 1}, meaning edges to vertices 0 and 2.

2. Step 2: Trace loop printing neighbors

   Loop checks graph[1][i] == 1; prints i when true. i=0 and i=2 satisfy condition.

3. Final Answer:

   0 2 -> Option A

4. Quick Check:

   Neighbors of vertex 1 = 0 and 2 [OK]

Hint: Check matrix row for 1s to find neighbors [OK]

Common Mistakes:

• Confusing row and column indices
• Printing vertex itself as neighbor
• Misreading matrix values

4. The following code attempts to create an adjacency list for a graph with 3 vertices but has an error:

int* graph[3];
for (int i = 0; i < 3; i++) {
  graph[i] = malloc(sizeof(int));
  graph[i][0] = i;
}

What is the main issue?

medium

A. Array size should be 4 instead of 3

B. Using malloc instead of calloc

C. Memory allocated is too small for multiple neighbors

D. graph should be declared as int graph[3][3]

Solution

1. Step 1: Check memory allocation size

   malloc(sizeof(int)) allocates space for only one int, but adjacency list needs space for multiple neighbors.

2. Step 2: Understand adjacency list needs dynamic size

   Allocating only one int is insufficient; should allocate enough space or use dynamic structures like linked lists.

3. Final Answer:

   Memory allocated is too small for multiple neighbors -> Option C

4. Quick Check:

   Insufficient malloc size = Error [OK]

Hint: Allocate enough memory for all neighbors in adjacency list [OK]

Common Mistakes:

• Confusing malloc and calloc
• Wrong array declaration type
• Assuming fixed size adjacency list

5. You have a graph with 1000 vertices and about 10,000 edges. You want to quickly check if an edge exists between any two vertices. Which representation is best and why?

hard

A. Adjacency List, because it uses less memory for sparse graphs

B. Adjacency Matrix, because it allows O(1) edge existence check

C. Edge List, because it is easiest to implement

D. Incidence Matrix, because it stores edges explicitly

Solution

1. Step 1: Analyze graph size and density

   1000 vertices and 10,000 edges means the graph is moderately dense (max edges ~499,500).

2. Step 2: Consider edge existence check speed

   Adjacency matrix allows checking edge existence in O(1) time by direct index access.

3. Step 3: Compare memory vs speed tradeoff

   Though adjacency matrix uses more memory, fast edge check is priority here.

4. Final Answer:

   Adjacency Matrix, because it allows O(1) edge existence check -> Option B

5. Quick Check:

   Fast edge check = Adjacency Matrix [OK]

Hint: Need fast edge check? Use adjacency matrix despite memory [OK]

Common Mistakes:

• Choosing adjacency list only for memory without speed need
• Ignoring graph density impact
• Confusing edge list with adjacency matrix