When I’m debugging a graph problem under time pressure—route constraints, dependency rules, access control checks—the fastest wins usually come from choosing the right representation. If you’ve ever asked “Is there an edge between these two nodes?” a few million times inside a tight loop, you’ve felt the pain of a slow lookup. That’s where an adjacency matrix earns its keep: constant-time edge checks with a simple, predictable memory layout.

You’re going to build an adjacency matrix in Python from an edge list (tuples like (u, v)), then you’ll extend it to handle directed graphs, weights, labels, self-loops, and multi-edges. I’ll also show how I use adjacency matrices in real tasks: degree queries, neighbor extraction, and even path counting via matrix multiplication. Finally, we’ll talk plainly about tradeoffs—because an adjacency matrix is a terrible idea for many graphs, and I want you to recognize those cases early.

Adjacency Matrix: the mental model

Picture a spreadsheet. Rows are “from” vertices, columns are “to” vertices, and the cell (i, j) tells you whether there’s an edge from i to j.

• For an unweighted graph, each cell is typically 0 (no edge) or 1 (edge exists).
• For a weighted graph, the cell can store a number like 7 (cost, distance, capacity), and a sentinel like 0 or None means “no edge”.
• For an undirected graph, the matrix is symmetric: M[u][v] == M[v][u].
• For a directed graph, symmetry is not expected: u -> v and v -> u are independent.

Why I like this structure: asking “Is there an edge from u to v?” becomes a single index operation: M[u][v]. No searching. No hashing. Just indexing.

The cost: the matrix has V * V cells. Memory grows quadratically. That one fact is the entire story behind when this representation is great and when it’s a trap.

Build an adjacency matrix from an edge list (the core pattern)

If your vertices are numbered 0..V-1, building the matrix is straightforward:

• Create a V x V matrix filled with zeros.
• For each edge (u, v), set matrix[u][v] = 1.
• If the graph is undirected, also set matrix[v][u] = 1.

Here’s a complete, runnable implementation that matches that pattern and prints the sample outputs you’d expect.

from future import annotations
from typing import Iterable, List, Sequence, Tuple
def createadjacencymatrix(V: int, edges: Iterable[Tuple[int, int]], *, undirected: bool = True) -> List[List[int]]:
if V < 0:
raise ValueError(‘V must be non-negative‘)
matrix: List[List[int]] = [[0] * V for _ in range(V)]
for u, v in edges:
if not (0 <= u < V) or not (0 <= v < V):
raise ValueError(f‘Edge ({u}, {v}) contains a vertex outside 0..{V-1}‘)
matrix[u][v] = 1
if undirected:
matrix[v][u] = 1
return matrix
def print_matrix(matrix: Sequence[Sequence[int]]) -> None:
for row in matrix:
print(list(row))
Example 1
V1 = 3
edges1 = [(0, 1), (1, 2), (2, 0)]
printmatrix(createadjacency_matrix(V1, edges1))
print()
Example 2
V2 = 4
edges2 = [(0, 1), (1, 2), (1, 3), (2, 3), (3, 0)]
printmatrix(createadjacency_matrix(V2, edges2))

A note on complexity (because this is a common place where people say the wrong thing):

• Initializing the V x V list-of-lists touches V^2 cells, so that part is O(V^2).
• Filling edges is O(E).
• Total time is O(V^2 + E), and space is O(V^2).

If you truly need build-time closer to O(E), you’re looking for a sparse representation (adjacency lists, sets, or a sparse matrix type). I’ll get to that later.

Getting the details right: directed graphs, self-loops, and duplicate edges

In production code, edge lists are messy. Here are the edge cases I handle up front.

Directed vs undirected

For directed graphs, you only set matrix[u][v]. That’s it.

V = 3
edges = [(0, 1), (1, 2)]
M = createadjacencymatrix(V, edges, undirected=False)



M[1][0] stays 0

Self-loops

A self-loop is an edge like (2, 2). In an adjacency matrix, that lands on the diagonal M[2][2].

• For simple graphs, you might disallow these.
• For state machines, DP graphs, or Markov chains, self-loops can be meaningful.

If you want to forbid them:

def createsimplegraph_matrix(V: int, edges: Iterable[Tuple[int, int]], *, undirected: bool = True) -> List[List[int]]:
matrix = [[0] * V for _ in range(V)]
for u, v in edges:
if u == v:
raise ValueError(f‘Self-loop not allowed: ({u}, {v})‘)
matrix[u][v] = 1



if undirected:
matrix[v][u] = 1
return matrix

Duplicate edges and multi-edges

If your input may contain duplicates (common when edges are generated from logs, merges, or incremental updates), the basic 0/1 matrix naturally deduplicates by overwriting 1 with 1. That’s often fine.

If you actually want to represent a multigraph (parallel edges), you can store counts instead of booleans:

from typing import Iterable, List, Tuple
def createadjacencycount_matrix(V: int, edges: Iterable[Tuple[int, int]], *, undirected: bool = True) -> List[List[int]]:
matrix = [[0] * V for _ in range(V)]
for u, v in edges:
matrix[u][v] += 1
if undirected and u != v:
matrix[v][u] += 1
return matrix

This is also handy when your “edges” represent repeated interactions: number of calls between services, number of messages between users, or number of flights between airports.

Weighted adjacency matrices (and how I avoid sentinel bugs)

Weighted graphs are where adjacency matrices get slightly tricky: you must choose a “no edge” value.

Common approaches:

• Use 0 to mean “no edge”, and positive numbers for weights.

– Works only if 0 is not a valid weight.

• Use None to mean “no edge”.

– Very explicit, but the matrix becomes Optional[float] and you’ll write more checks.

• Use math.inf as “no edge” when weights represent costs.

– Great for algorithms like Floyd–Warshall.

I usually pick None for correctness-first code, then switch to numeric sentinels when performance is tight and the domain is clean.

Here’s a weighted builder that supports both directed/undirected and multiple edges (keeping the smallest weight, which is what I want for shortest-path graphs).

from future import annotations
from typing import Iterable, List, Optional, Tuple
def createweightedadjacency_matrix(
V: int,
edges: Iterable[Tuple[int, int, float]],
*,
undirected: bool = True,
no_edge: Optional[float] = None,
keep: str = ‘min‘,
) -> List[List[Optional[float]]]:
if keep not in {‘min‘, ‘last‘}:
raise ValueError("keep must be ‘min‘ or ‘last‘")
matrix: List[List[Optional[float]]] = [[noedge] * V for  in range(V)]
def set_edge(a: int, b: int, w: float) -> None:
current = matrix[a][b]
if current is None or keep == ‘last‘:
matrix[a][b] = w
else:
matrix[a][b] = min(current, w)
for u, v, w in edges:
if not (0 <= u < V) or not (0 <= v < V):
raise ValueError(f‘Edge ({u}, {v}) contains a vertex outside 0..{V-1}‘)
set_edge(u, v, float(w))
if undirected:
set_edge(v, u, float(w))
return matrix

A subtle bug I see a lot: someone uses 0 as “no edge” and later introduces real edges with weight 0 (free transitions, promotions, same-zone moves). If you might ever have a legitimate 0, don’t use it as a sentinel.

When I choose math.inf instead of None

If I’m explicitly doing “cost to travel” math, I like math.inf because it composes well:

• min(current, candidate) works naturally.
• a + b remains inf if either is inf.

That makes all-pairs shortest paths (Floyd–Warshall) almost mechanical:

import math
from typing import Iterable, List, Tuple
def createweightmatrix_inf(V: int, edges: Iterable[Tuple[int, int, float]], *, undirected: bool = True) -> List[List[float]]:
dist = [[math.inf] * V for _ in range(V)]
for i in range(V):
dist[i][i] = 0.0
for u, v, w in edges:
w = float(w)
dist[u][v] = min(dist[u][v], w)
if undirected:
dist[v][u] = min(dist[v][u], w)
return dist

From integers to real-world IDs: mapping labels to matrix indices

In many real systems, vertices aren’t neat integers. They’re things like:

• microservice names (‘billing-api‘, ‘fraud-worker‘)
• airports (‘SFO‘, ‘JFK‘)
• packages (‘requests‘, ‘urllib3‘)

You can still use an adjacency matrix—just create a stable index mapping.

from future import annotations
from typing import Dict, Iterable, List, Sequence, Tuple
def build_index(labels: Sequence[str]) -> Dict[str, int]:
index: Dict[str, int] = {}
for i, label in enumerate(labels):
if label in index:
raise ValueError(f‘Duplicate label: {label!r}‘)
index[label] = i
return index
def creatematrixfromlabelededges(
labels: Sequence[str],
edges: Iterable[Tuple[str, str]],
*,
undirected: bool = True,
) -> List[List[int]]:
idx = build_index(labels)
V = len(labels)
matrix = [[0] * V for _ in range(V)]
for a, b in edges:
u = idx[a]
v = idx[b]
matrix[u][v] = 1
if undirected:
matrix[v][u] = 1
return matrix
services = [‘gateway‘, ‘billing‘, ‘fraud‘, ‘email‘]
deps = [(‘gateway‘, ‘billing‘), (‘billing‘, ‘fraud‘), (‘gateway‘, ‘email‘)]
M = creatematrixfromlabelededges(services, deps, undirected=False)

In my experience, the mapping is where mistakes happen:

• inconsistent label casing (‘SFO‘ vs ‘sfo‘)
• hidden whitespace (‘billing‘ vs ‘billing ‘) from CSVs
• edges referencing unknown labels

I usually normalize labels early (strip whitespace, enforce a case rule) and fail fast when an unknown label appears.

A “trust nothing” labeled-edge loader

If edges come from external input (CSV, logs, user data), I like a loader that can either fail fast or quietly skip bad lines, depending on the use case:

from future import annotations
from dataclasses import dataclass
from typing import Dict, Iterable, Iterator, List, Sequence, Tuple
@dataclass(frozen=True)
class BadEdge:
src: str
dst: str
reason: str
def normalize_label(s: str) -> str:
return s.strip()
def labelededgesto_indices(
labels: Sequence[str],
edges: Iterable[Tuple[str, str]],
*,
strict: bool = True,
) -> Tuple[List[Tuple[int, int]], List[BadEdge]]:
idx: Dict[str, int] = {normalize_label(lbl): i for i, lbl in enumerate(labels)}
ok: List[Tuple[int, int]] = []
bad: List[BadEdge] = []
for a, b in edges:
a2 = normalize_label(a)
b2 = normalize_label(b)
if a2 not in idx:
msg = f‘unknown label: {a!r}‘
if strict:
raise ValueError(msg)
bad.append(BadEdge(a, b, msg))
continue
if b2 not in idx:
msg = f‘unknown label: {b!r}‘
if strict:
raise ValueError(msg)
bad.append(BadEdge(a, b, msg))
continue
ok.append((idx[a2], idx[b2]))
return ok, bad

That one utility has saved me a lot of time when debugging “why is the matrix empty?” problems.

Working with the matrix: queries, degrees, neighbors, and fast checks

Once you have M, don’t treat it as just a printout. Use it.

Edge existence checks

This is the classic reason to choose a matrix.

if M[u][v] == 1:
# edge exists
...

Degree of a vertex

For an undirected unweighted graph, the degree is the sum of a row (or column):

def degree(matrix: List[List[int]], u: int) -> int:
return sum(matrix[u])

For directed graphs, you often want both:

• out-degree: sum(row)
• in-degree: sum of column

def out_degree(matrix: List[List[int]], u: int) -> int:
return sum(matrix[u])
def in_degree(matrix: List[List[int]], v: int) -> int:
return sum(matrix[u][v] for u in range(len(matrix)))

Neighbors of a vertex

Adjacency lists give neighbors instantly; matrices don’t. You have to scan a row.

def neighbors(matrix: List[List[int]], u: int) -> List[int]:
return [v for v, hasedge in enumerate(matrix[u]) if hasedge]

This scan is O(V) per vertex. That’s acceptable for dense graphs, but it’s a red flag for sparse ones.

Updating edges

If you’re doing incremental updates (feature flags enabling routes, toggling permissions), a matrix is clean:

def add_edge(matrix: List[List[int]], u: int, v: int, *, undirected: bool = True) -> None:
matrix[u][v] = 1
if undirected:
matrix[v][u] = 1
def remove_edge(matrix: List[List[int]], u: int, v: int, *, undirected: bool = True) -> None:
matrix[u][v] = 0
if undirected:
matrix[v][u] = 0

This kind of update pattern is one reason I still reach for adjacency matrices in simulation code and constraint solvers.

A compact “API” I like for matrix graphs

When codebases grow, direct indexing everywhere (M[u][v]) can become hard to audit. If I’m going to keep a matrix around for a while, I often wrap it in a tiny helper that enforces invariants (like undirected symmetry) and keeps edge-check semantics consistent.

from future import annotations
from dataclasses import dataclass
from typing import List
@dataclass
class MatrixGraph:
matrix: List[List[int]]
undirected: bool = True
@property
def V(self) -> int:
return len(self.matrix)
def has_edge(self, u: int, v: int) -> bool:
return self.matrix[u][v] != 0
def add_edge(self, u: int, v: int) -> None:
self.matrix[u][v] = 1
if self.undirected:
self.matrix[v][u] = 1
def remove_edge(self, u: int, v: int) -> None:
self.matrix[u][v] = 0
if self.undirected:
self.matrix[v][u] = 0

It’s not “more optimal,” it’s just harder to misuse.

Matrices unlock matrix math: path counting and transitive closure

Here’s the “spreadsheet becomes algebra” moment.

For an unweighted directed graph with adjacency matrix A:

• A[i][j] tells you whether there’s a 1-step edge.
• (A^2)[i][j] tells you how many distinct 2-step walks exist from i to j.
• (A^k)[i][j] counts k-step walks.

This is not the same as “simple paths” (walks can repeat vertices), but it’s incredibly useful for reachability heuristics, small-state systems, and counting flows in constrained graphs.

In Python, plain list-of-lists multiplication is slow for large V, so when I do this I switch to NumPy.

import numpy as np
def adjacencymatrixnumpy(V: int, edges: list[tuple[int, int]], *, undirected: bool = True) -> np.ndarray:
A = np.zeros((V, V), dtype=np.int8)
for u, v in edges:
A[u, v] = 1
if undirected:
A[v, u] = 1
return A
V = 4
edges = [(0, 1), (1, 2), (2, 3), (0, 3)]
A = adjacencymatrixnumpy(V, edges, undirected=False)
A2 = A @ A
print(A)
print(A2)

A practical warning: dtype=np.int8 is fine for “is there an edge?” but it will overflow fast if you do repeated multiplications for path counting. For path counts, I use np.int64 (or even Python int via dtype=object if the counts can explode).

Transitive closure (reachability) with a matrix

You can compute reachability (is there any path from i to j?) using a transitive closure algorithm. For small-to-medium V, Warshall/Floyd–Warshall-style loops are easy to implement and easy to reason about.

Here’s a boolean transitive closure that does the right logical update:

from future import annotations
from typing import List
def transitive_closure(matrix: List[List[int]]) -> List[List[int]]:
V = len(matrix)
reach = [row[:] for row in matrix]
for k in range(V):
for i in range(V):
if not reach[i][k]:
continue
rik = reach[i][k]
row_k = reach[k]
row_i = reach[i]
for j in range(V):
if rowi[j] or (rik and rowk[j]):
row_i[j] = 1
return reach

That’s O(V^3), so I don’t use it for huge graphs. But for permission graphs, workflow automations, and small dependency networks, it’s practical.

All-pairs shortest paths (Floyd–Warshall) is “made for matrices”

If your graph is weighted and V is not too large, Floyd–Warshall reads beautifully with an adjacency matrix.

import math
from typing import List
def floyd_warshall(dist: List[List[float]]) -> List[List[float]]:
V = len(dist)
d = [row[:] for row in dist]
for k in range(V):
dk = d[k]
for i in range(V):
dik = d[i][k]
if dik == math.inf:
continue
di = d[i]
for j in range(V):
cand = dik + dk[j]
if cand < di[j]:
di[j] = cand
return d

The key idea: a matrix makes “update all pairs (i, j) through intermediate k” a direct indexing operation.

Performance and memory in 2026: what I recommend (and what I avoid)

If you only remember one rule: adjacency matrices are for dense graphs or for problems dominated by edge-existence checks.

A plain V x V Python list-of-lists is simple, but it’s not memory-efficient, and Python integers are heavy. For anything beyond a few thousand vertices, you should pause and do the math.

Here’s how I compare options in real projects:

Approach

Best When

Typical Downsides

What I reach for in 2026

—

—

—

—

List-of-lists [[0]*V for _ in range(V)]

Small graphs, teaching, quick scripts

High memory per cell, slower math ops

Baseline, then refactor if needed

NumPy dense array

Dense graphs, matrix operations (A @ A), fast scans

Still V^2 memory, requires NumPy

My default for dense numeric work

SciPy sparse matrix (CSR/CSC)

Sparse graphs with large V

More complex API, edge updates can be slower

My default for large sparse graphs

Adjacency sets {u: {v1, v2}}

Sparse graphs, traversal-heavy workloads

Edge checks are O(1) but with hashing overhead

Great for BFS/DFS and pathfinding### A practical “don’t do this” threshold

If V = 50_000, then V^2 = 2.5 billion cells. Even one byte per cell is ~2.5 GB, and Python won’t give you one byte per cell.

So when I see V climb into the tens of thousands, I stop thinking “matrix” unless the graph is truly dense and I’m in a numeric stack (NumPy/SciPy) with a clear budget.

What “dense” means in practice

People say “my graph is dense” casually, but I like to quantify it.

• Maximum possible directed edges (excluding self-loops): V*(V-1)
• Maximum possible undirected edges (excluding self-loops): V*(V-1)/2
• Density (roughly): E / (max possible edges)

If density is a few percent or higher, a matrix can start to make sense—especially if you’re doing lots of random edge checks. If density is tiny (common in dependency graphs, social graphs, road networks), a matrix is usually wasteful.

The silent killer: Python object overhead

Even if each matrix cell is just 0/1, a list-of-lists stores references to Python objects. It’s not “one bit per edge,” it’s “a lot of pointers,” plus the list headers, plus allocator fragmentation.

That’s why, as soon as V grows, I move to one of these:

• bytearray rows (compact 0/1 values)
• array(‘b‘) / array(‘I‘) (typed storage)
• NumPy dtype=bool or uint8
• SciPy sparse matrices

Sparse matrices when V is big and E is small

If you want adjacency-matrix semantics (matrix operations, linear algebra) without V^2 storage, use a sparse matrix.

Build a sparse CSR adjacency matrix (SciPy)

CSR (Compressed Sparse Row) is a good default for graph-like operations that feel row-oriented (neighbors/outgoing edges). Here’s a complete builder.

from future import annotations
from typing import Iterable, Tuple
def adjacencysparsecsr(V: int, edges: Iterable[Tuple[int, int]], *, undirected: bool = True):
import numpy as np
from scipy.sparse import csr_matrix
rows: list[int] = []
cols: list[int] = []
data: list[int] = []
for u, v in edges:
rows.append(u)
cols.append(v)
data.append(1)
if undirected and u != v:
rows.append(v)
cols.append(u)
data.append(1)
A = csr_matrix((np.array(data, dtype=np.int8), (np.array(rows), np.array(cols))), shape=(V, V))
A.sum_duplicates()  # merges duplicates
A.eliminate_zeros()
return A

A few things I watch for:

• If you add duplicates and care about boolean semantics, sum_duplicates() can produce values > 1. You can convert to boolean (A.astype(bool)) or clamp (A.data[:] = 1).
• CSR isn’t great for frequent single-edge updates (it can be expensive to mutate). For lots of incremental updates, I build in lilmatrix or dokmatrix then convert to CSR once.

Weighted sparse adjacency

Just store data as weights instead of ones. If you need “keep the minimum weight for duplicates,” it’s usually easiest to deduplicate before building the sparse matrix (e.g., using a dict keyed by (u, v)), then emit a clean edge list.

A more memory-friendly dense matrix in pure Python

If I need a dense matrix but I don’t want Python-int overhead, I use bytearray rows. You still pay V^2 memory, but the constant factors are dramatically better.

Boolean adjacency with bytearray

This is my go-to for medium-sized dense unweighted graphs where I want speed and compactness without bringing in NumPy.

from future import annotations
from typing import Iterable, List, Tuple
def createadjacencybyte_matrix(V: int, edges: Iterable[Tuple[int, int]], *, undirected: bool = True) -> List[bytearray]:
M = [bytearray(V) for _ in range(V)]
for u, v in edges:
M[u][v] = 1
if undirected:
M[v][u] = 1
return M
def has_edge(M: List[bytearray], u: int, v: int) -> bool:
return M[u][v] != 0

You still index the same way: M[u][v]. But values are small integers 0..255 stored compactly.

When bytearray is not enough

If you need weights larger than 255, bytearray won’t work. Then I either:

• move to NumPy (uint16, uint32, float32, etc.), or
• store per-row array(‘I‘) or array(‘f‘) (still not as convenient as NumPy, but typed).

Traversals with an adjacency matrix (and why I rarely do it)

You can run BFS/DFS with a matrix, but remember: neighbor discovery requires scanning a full row. That turns a typical O(V+E) traversal into O(V^2) in practice.

That said, for dense graphs, O(V^2) might be fine (because E is near V^2 anyway), and the simplicity is appealing.

BFS using a matrix

from collections import deque
from typing import List, Optional
def bfs_matrix(M: List[List[int]], start: int) -> List[Optional[int]]:
V = len(M)
parent: List[Optional[int]] = [None] * V
parent[start] = start
q = deque([start])
while q:
u = q.popleft()
row = M[u]
for v, has_edge in enumerate(row):
if has_edge and parent[v] is None:
parent[v] = u
q.append(v)
return parent

I’ll use this when:

• V is small/medium,
• the graph is dense, or
• I need a quick baseline implementation to validate an algorithm.

If I care about traversal performance on sparse graphs, I switch to adjacency lists/sets immediately.

Practical scenarios where adjacency matrices shine

Here are patterns where I’ve found matrices genuinely useful (not just “academic”).

1) Permission checks / access control

If your system has “roles” and “resources” (or services, or endpoints), adjacency matrices model “allowed transitions” or “allowed calls” cleanly.

• M[role][resource] = 1 means role can access resource.
• Checking permission is instant: if M[role][resource]: allow.

If you do permission checks constantly (hot path), the simplicity and cache-friendly access can matter.

2) Dependency rules and constraint solvers

I like matrices when constraints are basically boolean relations:

• “A conflicts with B”
• “Package X depends on Y”
• “Task i must come before task j”

Many of these turn into repeated checks inside loops.

3) Small-state systems (workflows, automata, Markov chains)

State machines often have tens to a few thousand states, and you might want:

• reachability (“can we ever get from state A to B?”)
• path counting (“how many 5-step sequences exist?”)
• closure (“which states are reachable at all?”)

Matrices support that kind of analysis naturally.

4) Dense similarity graphs

Sometimes you build a graph where edges represent similarity above a threshold. If that threshold is low, the graph gets dense fast. A matrix becomes reasonable, especially in NumPy.

Common pitfalls (the ones I keep seeing)

These are the mistakes I actively guard against.

Pitfall 1: The “shared rows” bug

This is the classic:

M = [[0]  V]  V  # BUG

All rows reference the same list, so M[0][1] = 1 also modifies every row at column 1.

Always do:

M = [[0] * V for _ in range(V)]

Pitfall 2: Wrong symmetry assumptions

I’ve seen directed graphs accidentally treated as undirected (or vice versa) because someone sets both [u][v] and [v][u] without thinking.

If it matters, I like adding a quick assertion check:

def assert_symmetric(M: list[list[int]]) -> None:
V = len(M)
for i in range(V):
for j in range(V):
if M[i][j] != M[j][i]:
raise AssertionError(f‘matrix not symmetric at ({i}, {j})‘)

Pitfall 3: Sentinel collisions in weighted graphs

If 0 can be a valid weight, don’t use 0 as “no edge.” Use None or math.inf.

Pitfall 4: NumPy dtype overflow

If you do A @ A repeatedly with small integer dtypes (int8, int16), you will overflow quickly.

My rule:

• boolean existence: dtype=bool or uint8
• path counts: int64
• probabilities: float64 (or float32 if you know what you’re doing)

Pitfall 5: Confusing “walks” with “simple paths”

Matrix powers count walks, not simple paths. Walks can revisit vertices and edges. That’s not wrong—it’s just different.

If you truly need simple path counting, that’s a different problem (often exponential in the worst case), and matrices won’t magically fix it.

Converting between representations (so you can choose late)

In real work, I often start with one representation, then convert once I see the shape of the workload.

Edge list -> adjacency matrix

You’ve already seen this: build a V x V structure and fill edges.

Adjacency matrix -> adjacency list

Useful when you realize you’re doing traversals and neighbor iteration a lot.

from typing import List
def matrixtoadj_list(M: List[List[int]]) -> List[List[int]]:
V = len(M)
adj: List[List[int]] = [[] for _ in range(V)]
for u in range(V):
row = M[u]
adj[u] = [v for v, hasedge in enumerate(row) if hasedge]
return adj

Adjacency list -> adjacency matrix

Useful when you decide edge-existence checks dominate.

from typing import Iterable, List
def adjlistto_matrix(adj: List[Iterable[int]]) -> List[List[int]]:
V = len(adj)
M = [[0] * V for _ in range(V)]
for u, nbrs in enumerate(adj):
for v in nbrs:
M[u][v] = 1
return M

Debugging and validation tricks I actually use

When matrices go wrong, they go wrong quietly. These are the checks I run.

1) Verify diagonal policy

Do you allow self-loops or not? Decide, then validate.

def assertnoself_loops(M: list[list[int]]) -> None:
for i, row in enumerate(M):
if row[i]:
raise AssertionError(f‘self-loop at {i}‘)

2) Verify edge count

For undirected simple graphs (no self-loops), total edges should be half the number of ones.

def count_ones(M: list[list[int]]) -> int:
return sum(sum(row) for row in M)
def undirectededgecount(M: list[list[int]]) -> int:
# Assumes symmetric and no double counting.
total = count_ones(M)
return total // 2

3) Spot-check with a slower reference

If I’m unsure about correctness, I’ll build both:

• adjacency set (reference)
• adjacency matrix (optimized)

Then I’ll compare random pairs (u, v) for agreement.

4) Pretty-print with headers for labeled graphs

If labels matter, raw rows are painful. I’ll print a small matrix with row/column labels during debugging (only for small V, obviously).

When NOT to use an adjacency matrix (my honest checklist)

If any of these are true, I think twice:

• V is large (tens of thousands+) and the graph is sparse.
• Workload is traversal-heavy (BFS/DFS, shortest path on sparse graphs).
• You need to store rich per-edge data (metadata, timestamps, multiple attributes).
• You frequently add/remove edges in a way that doesn’t batch well (in SciPy sparse formats).

In those cases, adjacency lists/sets or sparse matrices usually win.

A quick decision guide (what I pick first)

This is the mental flowchart I use:

• I need tons of has_edge(u, v) checks and V is manageable → matrix.
• I need neighbor iteration / traversal and E is near V → adjacency list/set.
• I need matrix math or linear algebra and the graph is dense → NumPy dense array.
• I need matrix math but the graph is sparse and big → SciPy sparse.

FAQ (short answers to common questions)

Is an adjacency matrix always 0/1?

No. It can store weights, counts, probabilities, capacities—anything that fits your problem. The key idea is: cell (u, v) directly encodes the relationship from u to v.

What’s the fastest adjacency matrix in Python?

If you stay pure Python, bytearray rows are a strong choice for unweighted graphs. If you can use NumPy, a dense ndarray is typically faster for bulk operations and scans.

Can I do Dijkstra with a matrix?

You can, but it’s rarely the best choice unless the graph is dense. Dijkstra’s typical advantage comes from adjacency lists (iterate only real neighbors). With a matrix, you’ll scan whole rows and lose that advantage.

Why do people still teach adjacency matrices if they’re “often a bad idea”?

Because they’re conceptually clean, easy to implement, and they enable a family of matrix-based algorithms (closure, path counting, all-pairs updates) that are awkward with other representations.

Final thought

An adjacency matrix is not “the best graph representation.” It’s a specialized tool. But when your workload is dominated by edge-existence checks, when the graph is dense, or when matrix-style algorithms match your problem, it’s one of the cleanest—and sometimes fastest—ways to get reliable results in Python.

If you tell me your rough V, E, and what operations you do most (edge checks vs traversal vs matrix math), I can recommend an implementation style (plain lists, bytearray, NumPy, or SciPy) and help you tune it.