SME
Data Structures & Algorithms · Problem type
Adjacency matrix or list size
Use this for “An undirected graph has 1000 vertices and 5000 edges. How many cells does its adjacency matrix take, and how many entries its adjacency list?”
This is an example. Type your own values to start a new problem.
M
=
n
2
L
=
n
+
(2
×
e
)
eₘₐₓ
Most edges
worked out (not typed)
Formulas
M
=
n
2
1,000,000
=
1,
000
2
L
=
n
+
2
×
e
11,000 = 1,000 + 2 × 5,000
eₘₐₓ
=
n
×
n
− 1
2
499,500
=
1,000
×
1,000 − 1
2
Assumptions
•
The graph is undirected and simple: no loops, and at most one edge between two vertices.
•
The matrix keeps one cell for every ordered pair of vertices, edge or not.
•
The list keeps one head per vertex, and each edge appears twice, once under each end.
Step-by-step
WE KNOW
n = 1,000, e = 5,000
FIND
matrix cells (M), list entries (L), most edges (eₘₐₓ)
Step 1 · Find matrix cells (M)
Use M = n²
One
cell
for
each
row
vertex
and
column
vertex:
n
rows
of
n
.
M
=
1,
000
2
M
=
1,000,000
Step 2 · Find list entries (L)
Use L = n + 2 × e
One head per vertex, and every edge listed at both of its ends.
L
=
1,000
+
2
×
5,000
L
=
1,000
+
10,000
L
=
11,000
Step 3 · Find most edges (eₘₐₓ)
Use eₘₐₓ = n × (n − 1) ÷ 2
Each
pair
of
vertices
has
at
most
one
edge,
and
there
are
n
(
n
− 1)
2
pairs.
eₘₐₓ
=
1,000
×
1,000 − 1
2
eₘₐₓ
=
1,000
×
999
2
eₘₐₓ
=
999,000
2
eₘₐₓ = 499,500
Check
Put the numbers back in. Both sides should match.
1,000,000
=
1,
000
2
✓
11,000 = 1,000 + 2 × 5,000 ✓
499,500
=
1,000
×
1,000 − 1
2
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Trees and graphs
Main lesson
Heap array indices
Use this for “A heap is stored in an array from index 0. What are the parent and children of the node at index 5?”
Preorder traversal of a search tree
Use this for “Insert 50, 30, 70, 20, 40, 60, 80 into an empty binary search tree. In what order does a preorder traversal visit the nodes?”