Representation

The survival page: the three ways to store a graph, and the traps that come from mixing those storage choices up. Graph Anatomy is the page before this one and owns the vocabulary (vertex, edge, degree, path, cycle, and how a graph relates to the tree you already know); Traversal is the page after and owns BFS/DFS.

1. The four properties that decide your code

Graph Anatomy defines these; what matters here is that each one changes what you have to write. Four yes/no questions account for almost every adjective attached to the word "graph," and each has a direct consequence:

Property	The question
	What changes in your code
Directed	does an edge let you travel one way only?
	You append the edge once instead of twice when building the adjacency list, and cycle detection needs the 3-colour version instead of parent-skip.
Weighted	do edges carry a cost, or are they just present?
	Neighbours become (node, weight) pairs, and "shortest" stops meaning "fewest hops" - BFS gives way to Dijkstra.
Connected	can every vertex reach every other?
	You need the outer loop. A single traversal call only covers one component, so every count/sweep is wrapped in for v in graph: if v not in visited.
Cyclic	can a walk return to where it started?
	You need visited at all. Trees can skip it; anything that might loop cannot.

2. Choosing a representation

All three representations edit the exact same edge set, live - toggle an edge anywhere (canvas, matrix, list) and watch the other two update:

Fig. Graph Builder

Graph

Matrix

A

B

C

D

E

F

G

H

A

B

C

D

E

F

G

H

List

A →

B →

C →

D →

E →[]

F →[]

G →[]

H →

Edges

CLASS = Directed, Disconnected, Cyclic

The trap that keeps recurring is pricing operations in the wrong currency:

Operation	Adjacency list	Adjacency matrix
Space	O(V + E)	O(V²) always
Is u-v an edge?	O(degree(u))	O(1) ← matrix's one superpower
Iterate u's neighbours	O(degree(u))	O(V) (scan the whole row)

⚠

Matrix cost is V², list cost is degree

A matrix is V² regardless of edges, and a list's currency is degree, not V. Sizing the matrix by edge count is wrong - 10M nodes with zero edges is still 100 trillion cells; edges never shrink it. And pricing list ops in V is wrong - iterating a list node's neighbours costs O(degree), not O(V). In a V=100k, E=200k graph the average degree is ~4, so it's O(4), not O(100000). The list exists precisely to dodge the matrix's row-scan.

Adjacency matrix

An adjacency matrix is a V × V 2D array where cell (i, j) stores whatever describes the edge from vertex i to vertex j: 1 if you only care whether the edge exists, or the edge's weight if you need the cost. For an undirected graph the matrix is symmetric - M[i][j] == M[j][i] always - because an edge goes both ways; for a directed graph you write into exactly one of the two cells per edge, whichever direction it actually points. This is the right default only when the graph is small or genuinely dense and you need O(1) "is i connected to j" checks over and over.

Adjacency list

An adjacency list is an array of V buckets, one per vertex, where bucket i holds the vertices i connects to directly. For a weighted graph, each entry is a (neighbour, weight) pair instead of a bare neighbour id. This is the default representation for almost every graph problem, because real graphs are sparse - most vertices only touch a handful of others, so a list only pays for the edges that actually exist.

A real builder, undirected, with isolated vertices pre-initialised so they still show up with an empty neighbour list:

from collections import defaultdict

 

def build_adjacency_list(num_nodes, edges):

adj = defaultdict(list)

for i in range(num_nodes):

adj[i] = [] # pre-init so isolated nodes still appear

for start, end in edges:

adj[start].append(end)

adj[end].append(start) # both directions -> undirected

return adj

⚠

Dict keys 1 and '1' aren't the same key

Dict keys 1 and '1' are different keys. Pre-initialising isolated nodes with str(i) keys while the edges use int labels makes adj[1] and adj['1'] silently become two separate entries (1 == '1' is False). If half your graph vanishes, check that your node labels are all the same type.

Edge list

An edge list is the rawest form - just the raw connections, one entry per edge, such as [(0, 1), (1, 2), (0, 4)] (add a third value per tuple for weights). It's the most compact way to store a graph, but answering "who is next to X?" means scanning the whole list, so it's rarely used for traversal. It shines when an algorithm consumes the edges one at a time - most notably Kruskal's minimum-spanning-tree algorithm, which sorts the edge list and walks it in order.

3. Reversing the graph you were given

Not every graph problem should be solved on the graph you were handed. The cheapest and most reusable transformation is reversing it - flipping the direction of every edge - which turns a surprising number of "which vertices can reach X" questions into an ordinary traversal from X.

def reverse_graph(num_nodes, adj):

rev = [[] for _ in range(num_nodes)]

for u in range(num_nodes):

for v in adj[u]:

rev[v].append(u) # the edge u -> v becomes v -> u

return rev

In matrix form this is just the transpose: M_rev[i][j] == M[j][i], so an undirected graph is its own reverse (its matrix is symmetric) and reversing it is a no-op.

4. Building the graph from the input you were given

Almost no problem hands you an adjacency list. It hands you n plus a list of pairs, or a list of prerequisites, or two arrays of names, or a matrix. Getting from that to a traversable structure is five lines, and it is where a surprising share of wrong answers are actually born - the algorithm afterwards is fine.

The canonical builder

from collections import defaultdict

 

def build(n, edges, directed=False, weighted=False):

adj = {i: [] for i in range(n)} # pre-init: isolated vertices survive

for e in edges:

if weighted:

u, v, w = e

adj[u].append((v, w))

if not directed:

adj[v].append((u, w))

else:

u, v = e

adj[u].append(v)

if not directed:

adj[v].append(u) # the line people forget

return adj

Two decisions in there are the whole game: pre-initialising every vertex, and appending both directions exactly when the graph is undirected.

⚠

Building from edges alone loses isolated vertices

Building from the edge list alone loses every isolated vertex. A defaultdict(list) populated only by the edges has no key for a vertex that appears in no edge - so for u in adj skips it, connected-component counts come out too low, and len(adj) != n. Pre-initialise from range(n), and if n is not given you cannot infer it from the edges: the vertex count is input you must be handed.

⚠

One-direction edges make undirected graphs traverse wrong

Appending only one direction on an undirected graph makes the graph look right and traverse wrong. Every vertex still appears, every edge still exists, and a BFS from vertex 0 may even give the right answer on the sample - it just cannot walk "backwards" along any edge. The symptom is a component count that is too high or a path that is reported missing. When in doubt, assert the handshake lemma: sum(len(vs) for vs in adj.values()) == 2 * len(edges) for an undirected graph, and == len(edges) for a directed one.

Which way does [a, b] point?

This is the single most common direction error in graph problems, and it is worth slowing down for every single time.

def build_prerequisite_graph(num_courses, prerequisites):

adj = {i: [] for i in range(num_courses)}

indeg = [0] * num_courses

for course, prereq in prerequisites: # [a, b] = "a needs b"

adj[prereq].append(course) # edge b -> a: unlocks

indeg[course] += 1 # a is waiting on one more thing

return adj, indeg

⚠

The reversed graph answers a different question

The reversed graph is not a harmless variant - it answers a different question. With the edges built backwards, in-degree 0 selects the courses nothing depends on (the last ones), Kahn's still runs happily, and it still detects the cycle correctly - so a Course Schedule I submission that only returns True/False passes with the edges reversed. Course Schedule II, which returns the order, fails. That is why the bug survives to bite later: the cheap version of the problem cannot detect it.

Vertex labels that are not 0..n-1

The input gives	Do this	Watch out for
0-indexed integers	lists indexed directly - adj = [[] for _ in range(n)]	Nothing. This is the easy case.
1-indexed integers (common in "town judge", "network delay")	either allocate n + 1 slots and ignore index 0, or subtract 1 everywhere	Mixing the two conventions inside one function. Pick one at the top and never convert again.
strings ("JFK", "wine", variable names)	a dict of lists, or map each label to an index once up front	defaultdict growing silently, and the integer 1 and the string 1 being different dict keys.
an adjacency matrix	read neighbours as the column indices where the cell is set	Iterating row values instead of indices is the most persistent bug in graph code.
a grid	do not build anything - compute neighbours from offsets	Grids as Graphs

⚠

Mutating a defaultdict while iterating raises mid-loop

Iterating a defaultdict while indexing a missing key raises mid-loop. for u in graph: for v in graph[u]: ... graph[v] ... looks harmless, but touching graph[v] for a v that has no key creates it, and Python then throws RuntimeError: dictionary changed size during iteration. It is a crash rather than a wrong answer, which is the good news; the fix is to iterate list(graph), or to use graph.get(v, []), or to pre-initialise every vertex so no key is ever missing. Pre-initialising fixes this and the isolated-vertex bug at the same time.

⚠

Duplicate edges and self-loops are legal input

Duplicate edges and self-loops in the input are legal unless the problem forbids them. [[0,1],[1,0]] for one undirected edge, or [[2,2]], both appear in real test cases. A traversal survives both (the visited set absorbs them), but anything counting - degrees, edge totals, "is this a tree" via len(edges) == n - 1 - does not. If the problem does not promise a simple graph, deduplicate with a set of frozenset pairs before counting.

5. What graph algorithms actually cost

Every bound on this site is quoted in V and E, and the reason a traversal is O(V + E) rather than O(V * max_degree) is worth stating once: you visit each vertex once and, across the whole run, examine each vertex's neighbour list exactly once. Summing degree(v) over every vertex is 2E by the handshake lemma (Graph Anatomy), so the total neighbour work is O(E) no matter how lopsided the degrees are.

That argument depends on the representation. On an adjacency matrix there is no neighbour list - finding u's neighbours means scanning a full row of V cells whether or not they hold edges, so the same traversal becomes O(V^2):

Algorithm	Adjacency list	Adjacency matrix
DFS / BFS	O(V + E)	O(V^2)
Is u-v an edge?	O(degree(u))	O(1)
Dijkstra (binary heap)	O((V + E) log V)	O(V^2) with a linear min-scan, which wins when the graph is dense
Kruskal	O(E log E) - dominated by the sort	needs the edge list anyway; extracting it is O(V^2)
Prim	O(E log V)	O(V^2), again better on dense graphs
Floyd-Warshall	convert first; the algorithm is matrix-shaped	O(V^3)
Space	O(V + E)	O(V^2) always

Dijkstra with a Fibonacci heap is O(E + V log V), asymptotically better than the binary-heap O((V + E) log V), and it is what textbooks quote as the bound. Almost nobody implements it. The constant factors and pointer-chasing make it slower than a binary heap on any realistic input, and the lazy "decrease-key" it needs is fiddly to get right. The practical version does not even decrease keys - it pushes a duplicate entry and skips stale pops, which is the if d > dist[u]: continue line in the Dijkstra code. Asymptotically worse, universally faster.

The Python-specific costs

Trap	Cost	Fix
queue.pop(0) on a list	O(n) per call, so BFS silently becomes O(V^2)	collections.deque and popleft() - O(1)
Recursive DFS	dies at roughly 1000 frames	An explicit stack. Raising sys.setrecursionlimit trades a clean exception for a segfault, because the C stack does not grow with it.
if node in visited_list	O(n) per check	A set or a boolean list - O(1)
An adjacency matrix of Python lists	V^2 pointers at 8 bytes each - V = 10_000 is already about 800 MB	An adjacency list, or a bytearray / numpy array at 1 byte per cell
heapq with a mutable payload	comparison falls through to the second tuple element and can raise	Put a tie-breaking scalar before any object: (dist, node_id, payload)
Rebuilding a tuple key per grid cell	hashing dominates on big grids	Mark the grid in place, or index a flat list by r * cols + c

⚠

E can dominate the bound you assumed

E can be much larger than you assumed, and it changes which bound dominates. A complete graph has E around V^2/2, so O(V + E) is quadratic and O(E log E) is V^2 log V. Conversely a grid has E at about 2V, so everything is linear in the cell count. Before trusting a bound, put a number on both: "V = 10^5, E = 2*10^5" and "V = 10^3, E = 5*10^5" want different code even though both are "a big graph."

Where to go next

Traversal is the next page - BFS and DFS both consume whichever representation you just picked, via the same "neighbour function" idea introduced there.