Graphs

Most graph interview questions are decided before any algorithm is chosen, at the point where the candidate says what a vertex is. This guide starts there — modelling, including the state-space graphs where a vertex is a position plus accumulated state — and then works through the representations and their density trade-off, the two traversals and what each one actually guarantees, and the shortest-path algorithms with the weight assumptions that make them correct. It is deliberately specific about the errors that produce plausible wrong answers rather than crashes: marking visited at dequeue time, single-colour cycle detection on directed graphs, running Dijkstra over negative weights, and identifying a vertex by position when the transition depends on more.

modelling a problem as a graph

The hard part of a graph problem is usually deciding what the vertices and edges are, not running the algorithm.

A vertex is a state and an edge is a legal transition, which means the same physical objects can produce different graphs depending on the question.

Say what one vertex is before choosing an algorithm.

# "Fewest moves from A to B, carrying at most 3 keys."
# Vertex is NOT the cell. It is (row, col, keys_held):
start = (0, 0, frozenset())
# 100 x 100 grid with 3 keys -> 10,000 x 8 = 80,000 vertices, still trivial.

Interview trap. Assuming the vertices are the objects named in the problem misses the state-space graphs where a vertex is a position plus a remaining budget.

Engineering practice. Write down what one vertex represents in a sentence before choosing an algorithm, and check that every edge is a single legal move.

adjacency list versus adjacency matrix

An adjacency list costs space proportional to the edges and a matrix costs the square of the vertices, so the choice follows density.

The matrix answers 'is there an edge' in constant time and iterates a vertex's neighbours in time proportional to the vertex count; the list reverses both.

At V = 10,000 the matrix is 100,000,000 cells; the list is 2E.

Representation	Memory	edge(u,v)?	neighbours of u
List	O(V + E)	O(deg u)	O(deg u)
Matrix	O(V^2)	O(1)	O(V)

Traversal iterates neighbours, which is the operation the matrix does worst.

Interview trap. Using a matrix for a sparse graph wastes memory quadratically and makes neighbour iteration slower, which is the operation traversals actually perform.

Engineering practice. Default to the adjacency list, and use a matrix only for dense graphs or for algorithms that need constant-time edge queries.

complexity in terms of V and E

Graph complexities are stated in vertices and edges together, and collapsing them to a single n hides which one dominates.

Traversal is O(V + E), which is linear in the input size; the same algorithm on a dense graph is quadratic in V because E is quadratic.

O(V + E) is linear in the input, and quadratic when the graph is dense.

# Sparse road network: V = 1,000,000, E = 3,000,000 -> 4,000,000 steps.
# Dense social graph: V = 10,000, E = 50,000,000 -> traversal is O(V^2) in effect.

Interview trap. Quoting 'linear time' without saying linear in what is the standard imprecision, and it matters when the graph is dense.

Engineering practice. Always give the bound in both parameters, and say what E is in terms of V for the graph in question.

breadth-first search and shortest paths

Breadth-first search finds shortest paths in edge count, and only in edge count.

Because it explores in order of distance from the source, the first time it reaches a vertex is via a minimum-edge path.

Shortest in edge count only - weights break the guarantee.

from collections import deque
dist = {src: 0}
q = deque([src])
while q:
    u = q.popleft()
    for v in adj[u]:
        if v not in dist:
            dist[v] = dist[u] + 1     # first arrival is the minimum edge count
            q.append(v)

On a graph where A->B costs 100 and A->C->B costs 2, BFS still returns A->B.

Interview trap. Applying breadth-first search to a weighted graph gives the fewest-edge path, which is usually not the cheapest one.

Engineering practice. Use it for unweighted or uniformly weighted graphs, and move to Dijkstra as soon as weights differ.

marking visited at enqueue time

In breadth-first search a vertex must be marked visited when it is enqueued, not when it is dequeued.

Marking at dequeue time allows the same vertex to be enqueued once per incoming edge, which blows the queue up to the edge count.

Marking at dequeue lets a vertex enter the queue once per incoming edge.

for v in adj[u]:
    if v not in seen:
        seen.add(v)      # here - not after q.popleft()
        q.append(v)

On a complete graph of 10,000 vertices, dequeue-time marking queues up to 50,000,000 entries.

Interview trap. The version marking at dequeue is still correct, so the defect appears as a memory and time problem on dense graphs rather than as a wrong answer.

Engineering practice. Mark on enqueue, and assert that each vertex enters the queue at most once.

depth-first search and its uses

Depth-first search does not find shortest paths, and its value lies in the structure its traversal exposes.

The discovery and finish times of a depth-first walk reveal cycles, topological order, articulation points, and strongly connected components.

Structure, not distance: discovery and finish times are the product.

# DFS answers: is there a cycle, what is a topological order,
# which vertices are articulation points, what are the SCCs.
# It does not answer: what is the shortest path.

Interview trap. Substituting depth-first for breadth-first in a shortest-path problem produces a valid path that is not the shortest, which small test graphs rarely expose.

Engineering practice. Choose depth-first for structural questions and breadth-first for distance questions, and say which one the problem is asking.

recursion depth in depth-first search

Recursive depth-first search uses stack depth proportional to the longest path, which on a path-shaped graph is the vertex count.

Graphs derived from real data are often long and thin, so the overflow happens on production input rather than on test input.

A path graph of 10,000 vertices overflows at ~1,000 frames.

# Recursive DFS on a chain 0 -> 1 -> ... -> 9999: RecursionError.
stack = [src]                       # explicit stack: bounded only by memory
while stack:
    u = stack.pop()
    ...

Interview trap. Testing on small dense graphs never reaches the depth that a long chain produces.

Engineering practice. Use an explicit stack when the graph's shape is not controlled, and test with a path graph at the maximum expected size.

cycle detection in directed graphs

A directed graph has a cycle exactly when a depth-first search finds an edge back to a vertex still on the recursion stack.

Three colours are needed — unvisited, in progress, and finished — because an edge to a finished vertex is a cross edge, not a cycle.

Three colours: an edge to a finished vertex is not a cycle.

WHITE, GREY, BLACK = 0, 1, 2
def has_cycle(u):
    colour[u] = GREY
    for v in adj[u]:
        if colour[v] == GREY: return True        # back edge - a real cycle
        if colour[v] == WHITE and has_cycle(v): return True
    colour[u] = BLACK
    return False

# Diamond A->B, A->C, B->D, C->D is acyclic; a single visited set reports a cycle at D.

Interview trap. Using a single visited set reports a cycle whenever two paths reach the same vertex, which is a false positive on any directed acyclic graph with a diamond.

Engineering practice. Track the in-progress set separately from the visited set, and test on a diamond-shaped acyclic graph.

cycle detection in undirected graphs

In an undirected graph, an edge back to a visited vertex indicates a cycle only if it is not the edge just traversed.

Every undirected edge appears in both adjacency lists, so the parent vertex must be excluded from the check.

Exclude the edge you came in on, not merely the parent vertex.

def dfs(u, in_edge):
    for edge_id, v in adj[u]:
        if edge_id == in_edge: continue     # by edge, so parallel edges still count
        if v in seen or dfs(v, edge_id): return True
    return False

# Two parallel edges between the same pair are a genuine 2-cycle that parent-vertex checks miss.

Interview trap. Excluding by vertex identity is wrong when the graph has parallel edges, since a genuine two-edge cycle is then missed.

Engineering practice. Exclude by edge identity rather than by parent vertex when multi-edges are possible, and state which model the graph uses.

topological ordering

A topological order exists exactly for directed acyclic graphs, and any algorithm producing one also detects cycles.

Kahn's algorithm repeatedly removes vertices with no remaining incoming edges; if vertices remain when none can be removed, those vertices form a cycle.

Compare the emitted count with V, or a cyclic graph passes silently.

from collections import deque
indeg = {u: 0 for u in adj}
for u in adj:
    for v in adj[u]: indeg[v] += 1
q = deque(u for u in adj if indeg[u] == 0)
order = []
while q:
    u = q.popleft(); order.append(u)
    for v in adj[u]:
        indeg[v] -= 1
        if indeg[v] == 0: q.append(v)
if len(order) != len(adj): raise Cyclic(set(adj) - set(order))

Interview trap. Producing a partial order and reporting success without checking the output length silently accepts a cyclic graph.

Engineering practice. Compare the emitted vertex count with the total, and report the remaining vertices as the cycle evidence when they differ.

topological order is not unique

A directed acyclic graph usually has many valid topological orders, so tests must accept any of them.

The order depends on the queue discipline and on the vertex iteration order, both of which are implementation details.

Assert the property, not one sequence.

pos = {u: i for i, u in enumerate(order)}
assert all(pos[u] < pos[v] for u in adj for v in adj[u])   # every edge points forward

For A->C, B->C both [A, B, C] and [B, A, C] are correct.

Interview trap. Asserting one specific ordering makes the test fail after an unrelated refactor that changes iteration order.

Engineering practice. Assert the ordering property — every edge points forwards — rather than a specific sequence.

connected components

Counting components is a loop over vertices that starts a traversal from each unvisited one.

Each traversal marks a whole component, so the number of traversals started is the number of components and the total work is still O(V + E).

Loop over every vertex, or you find one component and call the graph connected.

components = 0
for u in vertices:
    if u not in seen:
        components += 1
        bfs(u)          # marks the whole component
# Total work is still O(V + E): each vertex and edge is touched once overall.

Interview trap. Starting a traversal only from the first vertex finds one component and reports the graph as connected.

Engineering practice. Loop over every vertex, and use the same guard for the disconnected case in every graph algorithm.

union-find

A disjoint-set structure answers connectivity questions incrementally, which a traversal cannot do without rerunning.

With path compression and union by rank the operations are effectively constant time, which is what makes Kruskal's algorithm and dynamic connectivity practical.

Near-constant per operation, and no deletion.

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]      # path halving
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb: return False
    if rank[ra] < rank[rb]: ra, rb = rb, ra
    parent[rb] = ra; rank[ra] += rank[ra] == rank[rb]
    return True

Interview trap. Assuming a union can be undone by reversing the last link is wrong, because path compression has already discarded the structure the rollback would need.

Engineering practice. Use it for incremental connectivity and minimum spanning trees, and say explicitly that deletions are outside its contract.

Dijkstra's algorithm

Dijkstra finds shortest paths from one source when every edge weight is non-negative, and the non-negativity is what makes it correct.

Extracting the smallest tentative distance finalises that vertex, because no later path through unfinalised vertices can be shorter when all weights are non-negative.

Non-negativity is the correctness condition, not a detail.

# Edges A->B = 2, A->C = 5, C->B = -4.
# Dijkstra finalises B at 2 and never reconsiders it; the true distance is 1.
# No error is raised - the answer is just wrong.

Interview trap. Running Dijkstra with a negative edge produces wrong answers silently, since a finalised vertex is never reconsidered.

Engineering practice. Check the weight domain first, and use Bellman-Ford when negative edges are possible.

the priority queue in Dijkstra

Dijkstra's complexity depends on the priority queue, and the practical implementation uses a binary heap with stale entries.

Rather than decreasing a key, the algorithm pushes an improved distance as a new entry and skips entries for already-finalised vertices on extraction.

Skip stale entries; the heap may hold O(E) of them.

import heapq
dist = {src: 0}; pq = [(0, src)]
while pq:
    d, u = heapq.heappop(pq)
    if d > dist.get(u, float("inf")): continue    # stale
    for v, w in adj[u]:
        nd = d + w
        if nd < dist.get(v, float("inf")):
            dist[v] = nd; heapq.heappush(pq, (nd, v))

Bound: O((V + E) log V).

Interview trap. Omitting the finalised check processes vertices more than once and can produce a wrong result under certain tie-breaking.

Engineering practice. Skip stale entries on extraction, and quote the bound as O((V + E) log V) for the heap-based version.

Bellman-Ford and negative cycles

Bellman-Ford handles negative edges and detects negative cycles, at the cost of O(VE) time.

Relaxing every edge V-1 times suffices for shortest paths; a further relaxation that still improves a distance proves a negative cycle is reachable.

V-1 rounds, then one more to detect the cycle.

for _ in range(V - 1):
    for u, v, w in edges:
        if dist[u] + w < dist[v]: dist[v] = dist[u] + w
for u, v, w in edges:
    if dist[u] + w < dist[v]: raise NegativeCycle(v)     # still improving: unbounded

O(VE): at V = 1,000 and E = 10,000 that is 10 million relaxations.

Interview trap. Reporting a shortest path in a graph with a reachable negative cycle is meaningless, because the path cost is unbounded below.

Engineering practice. Run the extra detection round, and report the cycle rather than a distance when one exists.

zero-one breadth-first search

When edge weights are only zero or one, a deque replaces the priority queue and the algorithm becomes linear.

Zero-weight edges push to the front and one-weight edges push to the back, which keeps the deque ordered by distance without a heap.

Zero-weight edges push to the front, so a deque replaces the heap.

from collections import deque
dq = deque([src])
while dq:
    u = dq.popleft()
    for v, w in adj[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            dq.appendleft(v) if w == 0 else dq.append(v)

O(V + E) instead of the heap-based O((V + E) log V).

Interview trap. Using a plain queue loses the ordering as soon as a zero-weight edge appears, and the distances become wrong rather than merely suboptimal.

Engineering practice. Recognise the zero-one weight structure and use the deque variant, stating the linear bound it achieves.

multi-source search

Shortest distance from any of several sources is found by seeding the queue with all of them at distance zero.

The traversal then computes the distance to the nearest source in one pass, rather than one pass per source.

Seed every source at distance zero; one pass, not one per source.

q = deque(sources)
for s in sources: dist[s] = 0        # all of them, before the loop
# 500 sources on a 1,000,000-vertex grid: one pass instead of 500.

Interview trap. Running the search once per source multiplies the cost by the source count and gives the same answer.

Engineering practice. Seed all sources before the loop, and use the same technique for multi-source Dijkstra with a heap.

bidirectional search

Searching from both endpoints towards the middle can reduce the explored frontier from exponential in the depth to exponential in half of it.

The two frontiers are expanded alternately and the search stops when they intersect, which requires reversible edges or an explicit reverse graph.

Two frontiers of depth d/2 instead of one of depth d.

# Branching factor 10, depth 6:
#   one direction   -> 10^6 = 1,000,000 nodes
#   both directions -> 2 x 10^3 = 2,000 nodes

Expand the smaller frontier each round, and check the meeting condition carefully.

Interview trap. The meeting condition must be checked correctly, or the reported path is not the shortest even though the endpoints connect.

Engineering practice. Expand the smaller frontier each round, and verify the result against a single-direction search on random graphs.

grids as implicit graphs

A grid is a graph whose vertices are cells and whose edges are the legal moves, and it usually needs no explicit adjacency structure.

Neighbours are computed by offset arithmetic and validated against the bounds and the obstacle map, so memory is proportional to the grid rather than to the edges.

Generate neighbours from an offset table; do not build the edge list.

MOVES = ((-1, 0), (1, 0), (0, -1), (0, 1))
def neighbours(r, c):
    for dr, dc in MOVES:
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#":
            yield nr, nc

A 1,000 x 1,000 grid has 1,000,000 vertices and ~4,000,000 edges: the explicit list is pure waste.

Interview trap. Building an explicit adjacency list for a large grid wastes memory that the implicit form does not need.

Engineering practice. Generate neighbours on demand from an offset table, and bounds-check before dereferencing.

state-space graphs

When a move depends on accumulated state, the vertex must include that state, which multiplies the graph size.

A position plus a set of collected keys, or a position plus remaining fuel, is one vertex, so the vertex count is the product of the two domains.

Include everything the transition depends on, or a better state is blocked.

seen = set()                     # keyed on (cell, keys), not cell
state = ((r, c), keys)
# Visiting (3,4) without the red key must not block reaching (3,4) with it.

Interview trap. Using position alone as the vertex marks a cell visited under one state and blocks reaching it under a better one.

Engineering practice. Include every component the transition depends on in the vertex identity, and check that the resulting state count is tractable.

reconstructing the path

Traversals compute distances; returning the path itself requires storing each vertex's predecessor.

The predecessor is recorded when a vertex is first reached or when its distance improves, and the path is rebuilt by walking backwards from the target.

Record predecessors during the search; re-running gives a different path.

parent = {src: None}
...
path, node = [], target
while node is not None: path.append(node); node = parent[node]
path.reverse()          # KeyError instead if target was never reached - handle it

Interview trap. Rebuilding the path by re-running the search from the target gives a path of the same length but not necessarily the same one.

Engineering practice. Store predecessors during the search and reverse the reconstruction, and handle the unreachable case explicitly.

bipartite testing

A graph is bipartite exactly when it can be two-coloured, which a single traversal decides.

Each vertex is coloured opposite to its parent, and an edge joining two equally coloured vertices proves an odd cycle and therefore non-bipartiteness.

Two-colour from every unvisited vertex, and return the conflicting edge.

colour = {}
for s in vertices:
    if s in colour: continue
    colour[s] = 0; q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in colour: colour[v] = 1 - colour[u]; q.append(v)
            elif colour[v] == colour[u]: return False, (u, v)     # odd cycle
return True, None

Interview trap. Testing only the component containing the first vertex reports bipartiteness for a graph whose other component is not.

Engineering practice. Run the colouring from every unvisited vertex, and return the conflicting edge as evidence when it fails.

memory as the real limit

Graph algorithms are usually bounded by memory rather than by time, because the visited set and the frontier are both proportional to the graph.

A breadth-first frontier on a wide graph can hold a large fraction of the vertices simultaneously, which is often larger than the adjacency structure itself.

The frontier, not the graph, is what usually runs out.

# 1,000,000-vertex grid: adjacency is implicit (0 bytes), visited set ~33 MB,
# and a BFS frontier across the widest cut can hold hundreds of thousands of
# entries at once. Estimate both before declaring the search feasible.

Interview trap. Estimating feasibility from the time bound alone ignores the frontier, which is what actually exhausts memory on large graphs.

Engineering practice. Estimate both, and consider iterative deepening or external-memory algorithms when the frontier does not fit.

choosing the algorithm

The algorithm follows from three questions: is the graph weighted, are the weights non-negative, and is the question about distance or structure.

Unweighted distance goes to breadth-first search, non-negative weights to Dijkstra, negative weights to Bellman-Ford, and structural questions to depth-first search or union-find.

Three questions decide it.

Weighted?	Negative?	Question	Algorithm
no	-	distance	BFS
yes	no	distance	Dijkstra
yes	yes	distance	Bellman-Ford
-	-	structure	DFS / union-find

Interview trap. Reaching for the most powerful algorithm avoids the decision and pays a complexity cost the problem did not require.

Engineering practice. Answer the three questions explicitly, and state the assumption that justifies the cheaper algorithm.