Adjacency List vs Matrix When to Choose Which in DSA C++ - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare an adjacency matrix for a graph with 4 nodes.

DSA C++

int graph[4][4] = [1];

Drag options to blanks, or click blank then click option'

A{{0}}

B{}

C{{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}

D{{1, 0, 0, 0}}

Attempts:

3 left

💡 Hint

Common Mistakes

Using a 1D array instead of 2D

Not initializing all elements

The adjacency matrix for 4 nodes is a 4x4 matrix initialized with zeros.

2fill in blank

medium

Complete the code to add an edge from node 1 to node 3 in an adjacency list.

DSA C++

adjList[1].[1](3);

Drag options to blanks, or click blank then click option'

Ainsert

Bpush_back

Cappend

Dadd

Attempts:

3 left

💡 Hint

Common Mistakes

Using insert instead of push_back

Using append which is Python syntax

In C++, adjacency lists use vectors and edges are added with push_back.

3fill in blank

hard

Fix the error in the code to check if an edge exists between node 2 and node 4 in an adjacency matrix.

DSA C++

if (graph[2][[1]] == 1) {
    // edge exists
}

Drag options to blanks, or click blank then click option'

A3

B4

C2

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using node number directly as index

Off-by-one errors

Node indices start at 0, so node 4 is index 3 in the matrix.

4fill in blank

hard

Fill both blanks to create an adjacency list for a graph with 3 nodes and add an edge from node 0 to node 2.

DSA C++

std::vector<int> adjList[[1]];
adjList[0].[2](2);

Drag options to blanks, or click blank then click option'

A3

Bpush_back

C4

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using insert instead of push_back

Wrong array size

We declare an array of vectors for 3 nodes and add an edge using push_back.

5fill in blank

hard

Fill all three blanks to initialize an adjacency matrix for 2 nodes and add an edge from node 0 to node 1.

DSA C++

int graph[[1]][[2]] = [3];
graph[0][1] = 1;

Drag options to blanks, or click blank then click option'

A2

B3

C{{0, 0}, {0, 0}}

D{{0, 1}, {0, 0}}

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing with wrong size

Pre-filling edges incorrectly

The matrix size is 2x2 for 2 nodes, initialized with zeros before adding edges.

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