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.