Representations — adjacency matrix (space O(V²)), adjacency list (space O(V+E)): Question bank

Before we start, one shared vocabulary so no symbol is unearned:

True or false — justify

Each item is a statement. The reveal says T/F and why — the "why" is the point.

Adjacency matrix always uses more space than adjacency list

False. On a dense graph

E = Θ (V^{2})

, so the list is also

Θ (V^{2})

; the space tie means the matrix's

O (1)

edge check makes it competitive, not worse.

An adjacency list uses

O (E)

space

False. It uses

O (V + E)

: you allocate one list header per vertex even for isolated (degree-0) vertices, so a graph with

V = 1 0^{6}

and

0

edges still costs

O (V)

For an undirected graph the adjacency matrix equals its own transpose

True. Edge

{u, v}

sets both

A [u] [v] = 1

and

A [v] [u] = 1

, so

A = A^{T}

— the grid is symmetric across the diagonal.

An undirected edge takes exactly one entry in an adjacency list

False. It is stored twice — once in

adj [u]

and once in

adj [v]

— so total entries

= 2 E

, keeping neighbor lookups symmetric.

Checking isEdge(u,v) is

O (1)

in an adjacency list

False. You must scan

u

's neighbor list, costing

O (de g u)

; only the matrix gives true

O (1)

via a direct index

A [u] [v]

Listing all neighbors of

u

costs

O (V)

in an adjacency list

False. It costs

O (de g u)

— you only touch the actual neighbors. The

O (V)

scan is the matrix's cost, because you must walk all

V

columns to find the few 1s.

Iterating over all edges is asymptotically equal in both representations

False. The matrix must inspect all

V^{2}

cells (

O (V^{2})

); the list visits only real entries (

O (V + E)

). This gap is exactly why BFS/DFS use lists.

Breadth-First Search (BFS) and Depth-First Search (DFS) run in

O (V + E)

regardless of representation

False. They are

O (V + E)

on an adjacency list; on a matrix each vertex's neighbor scan is

O (V)

, pushing the traversal to

O (V^{2})

A weighted graph cannot be stored in an adjacency matrix

False. Store the weight

w (u, v)

in the cell instead of a

1

, and use a sentinel (

\infty

or a special value) for "no edge."

Adding an edge is

O (1)

in both representations

True. Matrix: set one cell. List: push to the front of a list. Both are constant-time (assuming amortized push for dynamic arrays).

Spot the error

Each line is a wrong claim. The reveal names the flaw and corrects it.

"A social network of

1 0^{6}

users with ~100 friends each fits fine in a matrix."

Wrong.

V^{2} = 1 0^{12}

cells = terabytes, while the graph is sparse (

E \approx 5 \times 1 0^{7} ≪ V^{2}

). Compare

E

V^{2}

first — sparse means list.

(A^{2}) [u] [v]

counts the shortest path length from

u

v

Wrong. It counts the number of walks of length exactly 2, not a shortest distance.

(A^{k}) [u] [v]

= count of length-

k

walks; see Matrix Multiplication.

"For Floyd-Warshall Algorithm on

V = 400

you should use a list to save space."

Wrong. The algorithm indexes

dist [i] [j]

directly and needs

O (1)

edge weight lookups inside

O (V^{3})

loops; a

V^{2} = 1.6 \times 1 0^{5}

-cell matrix matches its access pattern perfectly.

"Because the matrix wastes cells, an empty graph costs

O (V + E) = O (V)

in it."

Wrong. The matrix cost is

O (V^{2})

independent of $E$ — you allocate every ordered pair's cell even for an empty graph. Only the list drops to

O (V)

when empty.

"An undirected graph's list has

E

entries, so it's smaller than a directed one's."

Wrong. Undirected stores each edge in both endpoints (

2 E

entries); a directed graph stores each edge once (

E

entries). Undirected costs more per edge, not less.

"The diagonal

A [u] [u]

is always 1."

Wrong. The diagonal is

0

unless self-loops are allowed;

A [u] [u] = 1

would falsely claim vertex

u

has an edge to itself.

"Dijkstra's Algorithm is always faster with a matrix because edge lookups are

O (1)

Wrong. Dijkstra repeatedly lists neighbors of the popped vertex; on a matrix that's

O (V)

per vertex →

O (V^{2})

total, worse than the list's

O (E lo g V)

on sparse graphs.

Why questions

Why is the matrix

O (V^{2})

even when the graph has almost no edges?

Because it reserves one cell for every ordered pair

(u, v)

—

V \times V

cells — and this allocation is decided by

V

alone, never by how many edges actually exist.

Why does one undirected edge create two list entries instead of one?

So that both

adj [u]

and

adj [v]

can answer "who are my neighbors?" symmetrically; storing it once would hide the edge from one endpoint's lookups.

Why do the two representations' space costs tie on dense graphs?

On a dense graph

E = Θ (V^{2})

, so the list's

O (V + E)

becomes

O (V^{2})

— the same order as the matrix. The saving of a list only exists when

E ≪ V^{2}

Why can the matrix answer isEdge(u,v) in

O (1)

but the list cannot?

The matrix indexes a fixed memory slot

A [u] [v]

directly; the list has no slot per pair, so it must search

u

's neighbor list, costing

O (de g u)

Why is the adjacency list the default choice in practice?

Most real-world graphs (road maps, social networks, web links) are sparse —

E

grows near-linearly in

V

— so

O (V + E)

storage and

O (de g u)

neighbor scans dominate the matrix. See Big-O Notation.

Why does

(A^{k}) [u] [v]

count walks, using Matrix Multiplication?

Each multiply sums over an intermediate vertex

m

(A^{2}) [u] [v] = \sum_{m} A [u] [m] A [m] [v]

adds 1 for every

m

that is a neighbor of both — i.e. every 2-step route — and induction extends this to length

k

Why does listing neighbors cost

O (V)

in a matrix but only

O (de g u)

in a list?

The matrix stores the neighbor info spread across a whole row of

V

cells (mostly 0s you must skip); the list stores only the actual neighbors contiguously.

Edge cases

Zero edges,

V = 1 0^{6}

: what does each representation cost?

Matrix still

O (V^{2}) = 1 0^{12}

cells (allocation ignores

E

); list drops to

O (V) = 1 0^{6}

— just the empty headers. The list crushes the matrix here.

A complete graph (every pair connected): which representation wins on space?

Neither on order —

E = (2 V) = Θ (V^{2})

so both are

O (V^{2})

. The matrix then wins on speed (

O (1)

edge checks), not space.

A single isolated vertex (degree 0): how many list entries does it hold?

Zero neighbor entries, but it still occupies one list header — this is exactly why the list bound keeps the

+ V

term in

O (V + E)

A self-loop edge

(u, u)

: how is it recorded?

In the matrix, set the diagonal cell

A [u] [u] = 1

(or its weight); in the list, add

u

adj [u]

. It counts as one edge touching

u

's degree (conventionally +2 in undirected degree, or +1 as an entry).

Maximum possible edges in an undirected simple graph on

V

vertices?

(2 V) = \frac{V ( V - 1 )}{2} = O (V^{2})

— every unordered pair connected once, no self-loops, so edges can never exceed the matrix's capacity.

A directed graph: how many list entries per edge, and is the matrix still symmetric?

One entry per directed edge

(u, v)

(only in

adj [u]

), giving

E

total entries; the matrix is not symmetric since

A [u] [v]

need not equal

A [v] [u]

V = 1

, no edges (a lone vertex): compare the two costs concretely.

Matrix: a

1 \times 1

grid = 1 cell. List: 1 empty header =

O (V) = O (1)

. A degenerate but valid case — both are constant, confirming the formulas hold at the boundary.

Active Recall

Recall Rapid re-test (cover and answer aloud)

Why is the matrix $O (V^{2})$ independent of $E$ ?
When do the two space costs become equal?
Why is isEdge $O (1)$ only in the matrix?
Why does BFS/DFS prefer the list?

Answers: 1) one cell per ordered pair, allocated by $V$ alone. 2) dense graphs, $E = Θ (V^{2})$ . 3) direct index vs list scan. 4) traversal is $O (V + E)$ on a list but $O (V^{2})$ on a matrix.