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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency matrix representation

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

DSA C++

#include <iostream>

int main() {
  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++) {
      std::cout << graph[i][j] << " ";
    }
    std::cout << std::endl;
  }
  return 0;
}

A

1 0 0 
0 1 0 
0 0 1 

B

0 1 1 
1 0 1 
1 1 0 

C

0 0 0 
0 0 0 
0 0 0 

D

1 1 1 
1 1 1 
1 1 1 

💡 Hint

Think about how undirected edges are represented symmetrically in the matrix.

In an undirected graph, edges are bidirectional, so the adjacency matrix is symmetric. The edges between nodes 0-1, 0-2, and 1-2 set those positions to 1 in both directions.

🧠 Conceptual

intermediate

Choosing adjacency list vs matrix for sparse graph

Which data structure is better for representing a graph with 1000 nodes but only 10 edges?

A Adjacency matrix because it allows faster edge lookup in sparse graphs.

B Adjacency matrix because it uses less memory for sparse graphs.

C Adjacency list because it stores all possible edges explicitly.

D Adjacency list because it uses less memory for sparse graphs.

💡 Hint

Think about memory usage when most nodes have very few edges.

Adjacency lists store only existing edges, so they use less memory for sparse graphs. Adjacency matrices always allocate space for all possible edges, which is wasteful here.

❓ 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 <iostream>
#include <vector>

int main() {
  std::vector<std::vector<int>> adj(3);
  adj[0].push_back(1);
  adj[0].push_back(2);
  adj[1].push_back(2);
  for(int i=0; i<3; i++) {
    std::cout << i << ": ";
    for(int v : adj[i]) {
      std::cout << v << " -> ";
    }
    std::cout << "null" << std::endl;
  }
  return 0;
}

A

0: 1 -> 2 -> null
1: 2 -> null
2: null

B

0: 2 -> 1 -> null
1: 2 -> null
2: null

C

0: null
1: 0 -> 2 -> null
2: null

D

0: 1 -> null
1: 2 -> 0 -> null
2: null

💡 Hint

Edges are directed and added only in one direction.

Edges 0->1 and 0->2 add nodes 1 and 2 to adjacency list of 0. Edge 1->2 adds node 2 to adjacency list of 1. Node 2 has no outgoing edges.

🧠 Conceptual

advanced

Time complexity for edge lookup

Which data structure provides O(1) time complexity to check if an edge exists between two nodes in a graph?

A Adjacency list because it stores edges in linked lists.

B Adjacency list because it uses hash maps internally.

C Adjacency matrix because it stores edges in a 2D array.

D Both adjacency list and matrix provide O(1) edge lookup.

💡 Hint

Think about direct access to edge information by indices.

Adjacency matrix uses a 2D array where each cell directly shows if an edge exists, so lookup is O(1). Adjacency lists require searching through neighbors, which is O(k) where k is degree.

🚀 Application

expert

Choosing graph representation for dense graph algorithms

You need to implement an algorithm that frequently checks if an edge exists between any two nodes in a graph with 500 nodes and 120,000 edges. Which representation is best and why?

A Adjacency matrix because it allows constant time edge checks despite higher memory use.

B Adjacency list because it uses less memory and is faster for dense graphs.

C Adjacency list because it allows faster iteration over all edges.

D Adjacency matrix because it uses less memory for dense graphs.

💡 Hint

Consider the trade-off between memory and speed for edge existence queries.

For dense graphs with many edges, adjacency matrix uses more memory but allows O(1) edge existence checks, which is critical for frequent queries. Adjacency lists require searching neighbors, slower for dense graphs.

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 List stores only existing edges, saving space for sparse graphs.

3. Final Answer:

   Adjacency List -> Option A

4. Quick Check:

   Sparse graph = Adjacency List [OK]

Hint: Sparse graphs use adjacency lists for space efficiency [OK]

Common Mistakes:

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

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

easy

A. int graph[5][5];

B. vector graph(5, vector<int>(5));

C. vector<int> graph(5);

D. int graph[5];

Solution

1. Step 1: Understand adjacency matrix structure

   An adjacency matrix is a 2D structure with size V x V for V vertices.

2. Step 2: Choose correct C++ declaration

   Using vector of vectors initializes a 5x5 matrix properly.

3. Final Answer:

   vector graph(5, vector<int>(5)); -> Option B

4. Quick Check:

   2D vector for adjacency matrix = vector graph(5, vector<int>(5)); [OK]

Hint: Adjacency matrix needs 2D structure, use vector [OK]

Common Mistakes:

• Using 1D array for adjacency matrix
• Not initializing inner vectors
• Confusing adjacency list syntax with matrix

3. Consider the following C++ code snippet for a graph with 3 vertices using adjacency list:

vector adj(3);
adj[0].push_back(1);
adj[1].push_back(2);
adj[2].push_back(0);
for (int i = 0; i < 3; i++) {
    cout << i << ": ";
    for (int v : adj[i]) cout << v << " ";
    cout << endl;
}

What is the output of this code?

medium

A. 0: 1 2
1: 0
2:

B. 0: 2
1: 0
2: 1

C. 0: 1
1: 2
2: 0

D. 0:
1: 2
2: 0 1

Solution

1. Step 1: Trace adjacency list insertions

   adj[0] has 1, adj[1] has 2, adj[2] has 0.

2. Step 2: Print adjacency list contents

   Loop prints each vertex and its adjacency: 0:1, 1:2, 2:0.

3. Final Answer:

   0: 1 1: 2 2: 0 -> Option C

4. Quick Check:

   Adjacency list print matches 0: 1 1: 2 2: 0 [OK]

Hint: Follow push_back calls to trace adjacency list output [OK]

Common Mistakes:

• Mixing up indices and values
• Assuming adjacency matrix output
• Forgetting to print spaces or newlines correctly

4. The following code attempts to create an adjacency matrix for a graph with 4 vertices but has a bug:

int graph[4][4];
for (int i = 0; i <= 4; i++) {
    for (int j = 0; j <= 4; j++) {
        graph[i][j] = 0;
    }
}

What is the main issue in this code?

medium

A. The inner loop should start from 1 instead of 0

B. The matrix is not initialized to zero

C. The graph size should be 5 instead of 4

D. The loops use <= causing out-of-bounds access

Solution

1. Step 1: Analyze loop bounds

   Loops run from 0 to 4 inclusive, which means 5 iterations each.

2. Step 2: Check array size and access

   Array size is 4x4, valid indices are 0 to 3. Index 4 causes out-of-bounds error.

3. Final Answer:

   The loops use <= causing out-of-bounds access -> Option D

4. Quick Check:

   Loop bounds exceed array size causing error [OK]

Hint: Use < instead of <= for array indices [OK]

Common Mistakes:

• Assuming array size is 5
• Thinking initialization is missing
• Changing loop start instead of end condition

5. You have a graph with 1000 vertices and about 10,000 edges. You need to perform frequent edge existence checks (i.e., is there an edge between vertex u and v?). Which representation is best and why? Choose the best option.

hard

A. Adjacency Matrix, because it allows O(1) edge existence checks despite higher space

B. Adjacency List, because it uses less space and edge checks are O(1)

C. Edge List, because it is simplest and fastest for edge checks

D. Adjacency Matrix, because it uses less space for sparse graphs

Solution

1. Step 1: Understand graph size and density

   1000 vertices and 10,000 edges is a sparse graph but with many edges.

2. Step 2: Compare edge existence check times

   Adjacency matrix allows O(1) edge check by direct index access; adjacency list requires searching neighbors.

3. Step 3: Consider space vs speed tradeoff

   Matrix uses more space but is faster for edge queries, which is needed here.

4. Final Answer:

   Adjacency Matrix, because it allows O(1) edge existence checks despite higher space -> Option A

5. Quick Check:

   Fast edge check needs adjacency matrix [OK]

Hint: For fast edge checks, adjacency matrix is best despite space [OK]

Common Mistakes:

• Assuming adjacency list gives O(1) edge checks
• Choosing edge list for fast queries
• Ignoring space vs time tradeoff