Graph representations (adjacency matrix vs list) in Data Structures Theory - Visual Side-by-Side Comparison

Concept Flow - Graph representations (adjacency matrix vs list)

Start with Graph

↓

Adjacency Matrix

↓

Create NxN matrix

↓

Mark edges with 1

↓

Access edge by index

↓

Use in algorithms

This flow shows how a graph can be represented either by a matrix or a list, starting from the graph and choosing the representation method.

Execution Sample

Data Structures Theory

Graph G with nodes: A, B, C
Edges: A-B, B-C
Adjacency Matrix:
  0 1 0
  1 0 1
  0 1 0
Adjacency List:
  A: [B]
  B: [A, C]
  C: [B]

This example shows a simple graph with three nodes and two edges represented as both an adjacency matrix and an adjacency list.

Analysis Table

Step	Operation	Adjacency Matrix State	Adjacency List State	Explanation
1	Initialize empty matrix and list	[[0,0,0],[0,0,0],[0,0,0]]	A: B: C:	Start with no edges marked
2	Add edge A-B	[[0,1,0],[1,0,0],[0,0,0]]	A: B B: A C:	Mark edge between A and B
3	Add edge B-C	[[0,1,0],[1,0,1],[0,1,0]]	A: B B: A, C C: B	Mark edge between B and C
4	Access edge A-C	Matrix[0][2] = 0	List A neighbors: ['B']	No direct edge between A and C
5	Access neighbors of B	Matrix row 1: [1,0,1]	List B neighbors: ['A','C']	B connected to A and C
6	End	Final matrix and list ready	Final matrix and list ready	Graph representation complete

💡 All edges processed and representations built

State Tracker

Variable	Start	After Step 2	After Step 3	Final
Adjacency Matrix	[[0,0,0],[0,0,0],[0,0,0]]	[[0,1,0],[1,0,0],[0,0,0]]	[[0,1,0],[1,0,1],[0,1,0]]	[[0,1,0],[1,0,1],[0,1,0]]
Adjacency List	A: B: C:	A: B B: A C:	A: B B: A, C C: B	A: B B: A, C C: B

Key Insights - 3 Insights

Why does the adjacency matrix use more space than the adjacency list?

The adjacency matrix always uses space for all possible node pairs (N x N), even if many edges don't exist, as shown in the matrix state in execution_table rows 1-3. The adjacency list only stores actual neighbors, so it uses less space for sparse graphs.

How do we check if two nodes are connected in each representation?

In the adjacency matrix, check the value at matrix[row][column] (execution_table step 4). In the adjacency list, check if one node appears in the other's neighbor list (execution_table step 4).

Why might adjacency lists be faster for iterating neighbors?

Because adjacency lists store only neighbors, iterating them (execution_table step 5) is faster than scanning an entire matrix row which includes zeros for non-neighbors.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the adjacency matrix value for edge B-C?

A 0

B 2

C 1

D -1

💡 Hint

Check the 'Adjacency Matrix State' column at step 3 in the execution_table

According to variable_tracker, what neighbors does node B have after step 3?

A []

B ["A", "C"]

C ["A"]

D ["C"]

💡 Hint

Look at the 'Adjacency List' row in variable_tracker after step 3

If the graph had 1000 nodes but only 10 edges, which representation would likely use less memory?

A Adjacency List

B Adjacency Matrix

C Both use the same memory

D Cannot tell from given info

💡 Hint

Refer to key_moments about space usage and execution_table showing sparse edges

Concept Snapshot

Graph representations:
- Adjacency Matrix: NxN grid, 1 if edge exists, 0 otherwise
- Adjacency List: Each node stores list of neighbors
- Matrix uses more space for large sparse graphs
- List is efficient for iterating neighbors
- Both represent same graph differently

Full Transcript

This visual execution shows how a graph with nodes A, B, and C and edges A-B and B-C is represented in two ways: adjacency matrix and adjacency list. We start with empty structures, then add edges step-by-step, updating the matrix cells and neighbor lists. The matrix is a 3x3 grid marking edges with 1s, while the list stores neighbors for each node. Checking connections differs: matrix uses index lookup, list checks neighbor presence. Matrix uses more space but allows quick edge checks; list uses less space and is faster to iterate neighbors. This helps understand when to use each representation.

Practice

1. Which graph representation uses a 2D grid to show connections between nodes?

easy

A. Incidence matrix

B. Adjacency matrix

C. Edge list

D. Adjacency list

Solution

1. Step 1: Understand adjacency matrix structure

   An adjacency matrix is a 2D grid where rows and columns represent nodes, and cells show if an edge exists.

2. Step 2: Compare with other representations

   Adjacency lists store neighbors in lists, not grids. Edge lists and incidence matrices differ in format.

3. Final Answer:

   Adjacency matrix -> Option B

4. Quick Check:

   2D grid = adjacency matrix [OK]

Hint: Matrix means grid; list means neighbors [OK]

Common Mistakes:

• Confusing adjacency list with matrix
• Thinking edge list is a grid
• Mixing incidence matrix with adjacency matrix

2. Which of the following is the correct way to represent an adjacency list in Python?

easy

A. graph = [[1, 2], 0, [0, 1]]

B. graph = [[0,1,0],[1,0,1],[0,1,0]]

C. graph = [(0,1), (1,2), (2,0)]

D. graph = {0: [1, 2], 1: [0], 2: [0, 1]}

Solution

1. Step 1: Identify adjacency list format

   An adjacency list maps each node to a list of its neighbors, often using a dictionary in Python.

2. Step 2: Check each option

   graph = {0: [1, 2], 1: [0], 2: [0, 1]} uses a dictionary with keys as nodes and values as neighbor lists, which is correct. graph = [[0,1,0],[1,0,1],[0,1,0]] is a matrix, C is an edge list, D incorrectly uses an integer 0 for node 1 instead of a list.

3. Final Answer:

   graph = {0: [1, 2], 1: [0], 2: [0, 1]} -> Option D

4. Quick Check:

   Dict with neighbors = adjacency list [OK]

Hint: Adjacency list uses dict with node keys [OK]

Common Mistakes:

• Choosing matrix format as list
• Confusing edge list with adjacency list
• Using integer instead of list for neighbors

3. Given the adjacency matrix below, which nodes are connected to node 1?
graph = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]

medium

A. Nodes 0 and 2

B. Nodes 1 and 2

C. Nodes 0 and 1

D. Nodes 2 only

Solution

1. Step 1: Locate row for node 1

   Row 1 in the matrix is [1, 0, 1], representing edges from node 1 to nodes 0, 1, and 2.

2. Step 2: Identify connected nodes

   Values 1 indicate connection. Here, positions 0 and 2 have 1, so node 1 connects to nodes 0 and 2.

3. Final Answer:

   Nodes 0 and 2 -> Option A

4. Quick Check:

   Row 1 has 1s at 0 and 2 [OK]

Hint: Check row for node, 1 means connected [OK]

Common Mistakes:

• Confusing row and column indices
• Including node itself as connected
• Misreading zeros as edges

4. What is wrong with this adjacency list representation?
graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: 1}

medium

A. Node 3's neighbors should be in a list

B. Node 1 has an invalid neighbor

C. Node 0 should not have neighbors

D. The graph should be an adjacency matrix

Solution

1. Step 1: Check format of neighbors for each node

   Nodes 0, 1, and 2 have neighbor lists. Node 3 has a single integer instead of a list.

2. Step 2: Identify correct adjacency list format

   Neighbors must always be in a list, even if only one neighbor exists, to keep consistent structure.

3. Final Answer:

   Node 3's neighbors should be in a list -> Option A

4. Quick Check:

   Neighbors must be lists [OK]

Hint: Neighbors always in lists, never single values [OK]

Common Mistakes:

• Ignoring single neighbor format
• Thinking adjacency list must be matrix
• Assuming neighbors can be integers

5. For a graph with 1000 nodes and only 10,000 edges, which representation is more memory efficient and why?

hard

A. Adjacency matrix, because it allows faster edge checks

B. Adjacency matrix, because it uses fixed size memory

C. Adjacency list, because it stores only existing edges

D. Adjacency list, because it stores all possible edges

Solution

1. Step 1: Calculate memory use for adjacency matrix

   An adjacency matrix for 1000 nodes uses 1000x1000 = 1,000,000 cells, regardless of edges.

2. Step 2: Calculate memory use for adjacency list

   An adjacency list stores only the 10,000 edges, so memory use is proportional to edges, much less than matrix.

3. Step 3: Compare efficiency

   Since edges are sparse compared to possible connections, adjacency list is more memory efficient.

4. Final Answer:

   Adjacency list, because it stores only existing edges -> Option C

5. Quick Check:

   Sparse graph = adjacency list efficient [OK]

Hint: Sparse graph? Use adjacency list for less memory [OK]

Common Mistakes:

• Choosing matrix for sparse graphs
• Confusing speed with memory use
• Thinking adjacency list stores all edges