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

Challenge - 5 Problems

🧠 Conceptual

intermediate

When to prefer adjacency list over adjacency matrix?

Which situation is best suited for using an adjacency list instead of an adjacency matrix to represent a graph?

A When the graph is dense with many edges close to the maximum possible

B When the graph is sparse with relatively few edges compared to vertices

C When the graph has a fixed small number of vertices and many edges

D When you need to quickly check if an edge exists between two vertices

💡 Hint

Think about memory usage and efficiency when edges are few.

An adjacency list uses less memory and is more efficient for sparse graphs because it stores only existing edges. An adjacency matrix always uses space proportional to the square of the number of vertices, which is wasteful for sparse graphs.

🧠 Conceptual

intermediate

When is adjacency matrix better than adjacency list?

In which case is using an adjacency matrix more advantageous than an adjacency list?

A When you need to quickly check if an edge exists between any two vertices

B When the graph is sparse and has very few edges

C When the graph has a very large number of vertices and edges

D When you want to save memory space

💡 Hint

Think about constant time edge lookup.

An adjacency matrix allows checking if an edge exists between two vertices in constant time O(1), which is faster than adjacency lists that may require searching through neighbors.

❓ Predict Output

advanced

Output of adjacency matrix representation

What is the printed adjacency matrix after adding edges (0->1), (1->2), and (2->0) in a graph with 3 vertices?

DSA Python

n = 3
adj_matrix = [[0]*n for _ in range(n)]
adj_matrix[0][1] = 1
adj_matrix[1][2] = 1
adj_matrix[2][0] = 1
for row in adj_matrix:
    print(row)

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

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

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

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

💡 Hint

Check which rows and columns have 1s based on edges.

The adjacency matrix has 1 at positions where an edge exists from row vertex to column vertex. So (0->1) sets adj_matrix[0][1] = 1, etc.

❓ Predict Output

advanced

Output of adjacency list after adding edges

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

DSA Python

n = 3
adj_list = {i: [] for i in range(n)}
adj_list[0].append(2)
adj_list[0].append(1)
adj_list[1].append(2)
for key in sorted(adj_list.keys()):
    print(f"{key}: {adj_list[key]}")

A

0: [2]
1: [2, 1]
2: []

B

0: [1, 2]
1: [2]
2: []

C

0: [2, 1]
1: [2]
2: []

D

0: [1]
1: [2]
2: [0]

💡 Hint

Check the order of append operations for vertex 0.

Edges are added in order: 0->2 then 0->1, so adjacency list for 0 is [2, 1]. Vertex 1 has [2], vertex 2 has no edges.

🧠 Conceptual

expert

Memory complexity comparison for large sparse graph

For a graph with 1 million vertices and 10 million edges, which representation is more memory efficient?

A Adjacency matrix, because it uses fixed size regardless of edges

B Neither, use edge list for better memory

C Both use about the same memory

D Adjacency list, because it stores only existing edges

💡 Hint

Consider the size of adjacency matrix as vertices squared.

An adjacency matrix for 1 million vertices requires 1 trillion entries, which is huge. An adjacency list stores only 10 million edges, much smaller and efficient for sparse 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 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 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 initialize an adjacency matrix for a graph with 4 vertices in Python?

easy

A. matrix = [[0 for _ in range(4)] for _ in range(4)]

B. matrix = [[0]*4]*4

C. matrix = [0]*4

D. matrix = [[None]*4 for _ in range(4)]

Solution

1. Step 1: Understand matrix initialization

   Using list comprehension with nested loops creates independent inner lists.

2. Step 2: Avoid shallow copies

   matrix = [[0]*4]*4 creates shallow copies causing all rows to reference the same list, leading to bugs.

3. Final Answer:

   matrix = [[0 for _ in range(4)] for _ in range(4)] -> Option A

4. Quick Check:

   Independent rows = matrix = [[0 for _ in range(4)] for _ in range(4)] [OK]

Hint: Use nested list comprehension for independent rows [OK]

Common Mistakes:

• Using [[0]*4]*4 causes all rows to be the same object
• Initializing with single list for matrix
• Using None instead of 0 for adjacency matrix

3. Consider the following Python code for a graph with 3 vertices using adjacency list representation:

graph = {0: [1, 2], 1: [2], 2: []}
print(graph[1])

What is the output?

medium

A. [1, 2]

B. []

C. [2]

D. KeyError

Solution

1. Step 1: Understand adjacency list structure

   Key 1 maps to list [2], meaning vertex 1 connects to vertex 2.

2. Step 2: Print value for key 1

   graph[1] returns [2], so print outputs [2].

3. Final Answer:

   [2] -> Option C

4. Quick Check:

   graph[1] = [2] [OK]

Hint: Access adjacency list by vertex key [OK]

Common Mistakes:

• Confusing keys and values in dictionary
• Expecting all vertices in output
• Assuming KeyError for existing key

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

matrix = [[0]*3]*3
matrix[0][1] = 1
print(matrix)

What is the output and what is the bug?

medium

A. IndexError; Wrong indexing

B. [[0, 1, 0], [0, 0, 0], [0, 0, 0]]; No bug

C. [[0, 0, 0], [0, 0, 0], [0, 0, 0]]; Assignment failed

D. [[0, 1, 0], [0, 1, 0], [0, 1, 0]]; Rows are shallow copies

Solution

1. Step 1: Understand matrix initialization

   Using [[0]*3]*3 creates 3 references to the same inner list.

2. Step 2: Modify one element affects all rows

   Setting matrix[0][1] = 1 changes the second element in all rows because they share the same list.

3. Final Answer:

   [[0, 1, 0], [0, 1, 0], [0, 1, 0]]; Rows are shallow copies -> Option D

4. Quick Check:

   Shallow copy rows cause all rows to change [OK]

Hint: Avoid [[0]*n]*n; use nested list comprehension [OK]

Common Mistakes:

• Assuming only first row changes
• Ignoring shallow copy behavior
• Confusing IndexError with shallow copy bug

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

hard

A. Edge List, because it is simplest to implement

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

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

D. Incidence Matrix, because it stores edges explicitly

Solution

1. Step 1: Analyze graph density and operations

   Graph has 1000 vertices and 10,000 edges, which is moderately sparse but not very sparse.

2. Step 2: Consider operation speed for edge checks

   Adjacency matrix allows checking edge existence in constant time O(1), while adjacency list requires searching neighbors.

3. Step 3: Balance memory and speed

   Though adjacency matrix uses more memory, the speed benefit for frequent edge checks outweighs memory cost here.

4. Final Answer:

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

5. Quick Check:

   Frequent edge check = Adjacency Matrix [OK]

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

Common Mistakes:

• Choosing adjacency list only for memory without considering speed
• Ignoring operation frequency in choice
• Confusing edge list with adjacency matrix for fast checks