Adjacency List vs Matrix When to Choose Which in DSA C++ - Key Differences

Recall & Review

beginner

What is an adjacency list in graph representation?

An adjacency list stores each vertex and a list of its connected neighbors. It uses less space for sparse graphs.

beginner

What is an adjacency matrix in graph representation?

An adjacency matrix is a 2D array where each cell (i, j) shows if there is an edge between vertex i and vertex j. It uses more space but allows quick edge checks.

intermediate

When is it better to use an adjacency list over an adjacency matrix?

Use adjacency list when the graph is sparse (few edges) because it saves memory and is efficient for iterating neighbors.

intermediate

When is an adjacency matrix preferred?

Use adjacency matrix when the graph is dense (many edges) or when you need to quickly check if an edge exists between two vertices.

intermediate

What is the space complexity difference between adjacency list and matrix?

Adjacency list uses O(V + E) space, where V is vertices and E is edges. Adjacency matrix uses O(V²) space regardless of edges.

Which graph representation uses less memory for a graph with very few edges?

A Adjacency List

B Adjacency Matrix

C Both use the same memory

D Depends on the number of vertices only

Adjacency list stores only existing edges, so it uses less memory for sparse graphs.

Which representation allows O(1) time to check if an edge exists between two vertices?

A Adjacency Matrix

B Neither supports O(1) edge check

C Both have O(1) time

D Adjacency List

Adjacency matrix uses a 2D array, so checking an edge is a direct index lookup.

For a graph with 1000 vertices and 10,000 edges, which representation is more space efficient?

A Cannot determine without edge distribution

B Adjacency Matrix

C Both are equally efficient

D Adjacency List

Adjacency list uses O(V + E) = 11,000, while matrix uses O(V²) = 1,000,000 cells.

Which representation is better for dense graphs?

A Depends on the algorithm

B Adjacency List

C Adjacency Matrix

D Neither is suitable

Adjacency matrix handles dense graphs well because it stores all edges explicitly.

Which representation is easier to iterate over all neighbors of a vertex?

A Adjacency Matrix

B Adjacency List

C Both are equally easy

D Depends on the graph size

Adjacency list stores neighbors directly, so iteration is straightforward and efficient.

Explain when and why you would choose an adjacency list over an adjacency matrix for graph representation.

Think about graphs with few edges compared to vertices.

Describe the advantages and disadvantages of using an adjacency matrix for graph representation.

Consider space and time trade-offs.

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