Adjacency List vs Matrix When to Choose Which in DSA Python - Visual Comparison

Concept Flow - Adjacency List vs Matrix When to Choose Which

Start: Need to represent graph

↓

Check graph size and density

↓

Use Adjacency List

↓

Less memory

↓

Efficient for

↓

iterating edges

↓

End

Decide graph representation by checking if graph is sparse or dense; use adjacency list for sparse graphs and adjacency matrix for dense graphs.

Execution Sample

DSA Python

graph_list = {0: [1, 2], 1: [2], 2: [0, 3], 3: []}
graph_matrix = [[0,1,1,0], [0,0,1,0], [1,0,0,1], [0,0,0,0]]

Shows a graph represented as adjacency list and adjacency matrix for the same graph.

Execution Table

Step	Operation	Graph Type	Memory Use	Edge Check Efficiency	Visual State
1	Initialize graph with 4 nodes and 4 edges	Adjacency List	Low (O(V+E))	Edge check slower (need to search list)	{0: [1,2], 1: [2], 2: [0,3], 3: []}
2	Initialize graph with 4 nodes and 4 edges	Adjacency Matrix	High (O(V^2))	Edge check fast (direct index)	[[0,1,1,0], [0,0,1,0], [1,0,0,1], [0,0,0,0]]
3	Check if edge 0->2 exists	Adjacency List	N/A	Search list of node 0	0's neighbors: [1,2] -> found 2
4	Check if edge 0->2 exists	Adjacency Matrix	N/A	Check matrix[0][2]	Value: 1 (edge exists)
5	Add edge 3->1	Adjacency List	Add 1 to list of node 3	Efficient append	{0: [1,2], 1: [2], 2: [0,3], 3: [1]}
6	Add edge 3->1	Adjacency Matrix	Set matrix[3][1] = 1	Direct index update	[[0,1,1,0], [0,0,1,0], [1,0,0,1], [0,1,0,0]]
7	Decide representation for large sparse graph	Adjacency List	Preferred	Better memory and iteration	Use adjacency list
8	Decide representation for small dense graph	Adjacency Matrix	Preferred	Fast edge checks	Use adjacency matrix
9	End	N/A	N/A	N/A	Decision based on graph size and density

💡 Decision made based on graph size and density; adjacency list for sparse, adjacency matrix for dense.

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 7	Final
graph_list	{}	{0: [1,2], 1: [2], 2: [0,3], 3: []}	{0: [1,2], 1: [2], 2: [0,3], 3: [1]}	Used for sparse graph	Final sparse graph representation
graph_matrix	[]	[[0,1,1,0], [0,0,1,0], [1,0,0,1], [0,0,0,0]]	[[0,1,1,0], [0,0,1,0], [1,0,0,1], [0,1,0,0]]	Used for dense graph	Final dense graph representation

Key Moments - 3 Insights

Why is adjacency list preferred for sparse graphs?

Because adjacency list uses memory proportional to edges and nodes (O(V+E)), which is efficient when edges are few, as shown in step 1 and step 7 of the execution_table.

Why is adjacency matrix better for dense graphs?

Adjacency matrix uses more memory (O(V^2)) but allows quick edge existence checks by direct indexing, as shown in steps 2 and 4.

How does adding an edge differ between list and matrix?

In adjacency list, adding an edge means appending to a list (step 5), while in matrix, it means setting a value at a specific index (step 6), which is faster but uses more memory.

Visual Quiz - 3 Questions

Look at the execution_table, at which step is the edge 3->1 added in the adjacency list?

A Step 5

B Step 6

C Step 3

D Step 7

💡 Hint

Check the 'Operation' and 'Graph Type' columns in execution_table rows 5 and 6.

According to variable_tracker, what is the state of graph_matrix after step 6?

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

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

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

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

💡 Hint

Look at the 'graph_matrix' row in variable_tracker after 'After Step 5' and 'After Step 7'.

If the graph is very large but has very few edges, which representation is best according to the execution_table?

A Adjacency Matrix

B Adjacency List

C Both are equally good

D Neither is suitable

💡 Hint

Refer to steps 7 and 8 in execution_table about graph size and density decisions.

Concept Snapshot

Adjacency List vs Matrix:
- Use adjacency list for sparse graphs (few edges).
- Use adjacency matrix for dense graphs (many edges).
- List uses less memory, matrix allows fast edge checks.
- Adding edges: list appends, matrix sets index.
- Choose based on graph size and edge density.

Full Transcript

This visual execution compares adjacency list and adjacency matrix graph representations. It starts by initializing both for a graph with 4 nodes and 4 edges. The adjacency list stores neighbors in lists, using less memory and slower edge checks. The adjacency matrix uses a 2D array, using more memory but allowing fast edge existence checks by direct indexing. Adding edges in the list means appending to a node's list, while in the matrix it means setting a value at a specific position. The decision to use list or matrix depends on graph size and density: sparse graphs favor adjacency lists for memory efficiency, dense graphs favor adjacency matrices for speed. The variable tracker shows how the graph structures change after operations. Key moments clarify why each representation suits different graph types. The quiz tests understanding of steps where edges are added, graph states, and representation choice based on graph properties.

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