Graphs and traversal

1. A graph is a dict of lists

Two representations, and one of them is the default.

Adjacency list. Key is a vertex, value is the vertices it connects to.

python

{
  'a': ['b', 'c'],
  'b': ['c'],
  'c': [],
}

Space is O(n + e): one key per vertex, including isolated ones, plus one entry per edge. Listing a vertex’s neighbours costs its degree. Asking whether two specific vertices are connected costs a scan of one list.

Adjacency matrix. A 2-D array where m[i][j] is 1 if there’s an edge.

Space is n² regardless of how many edges exist. “Are these two connected” is O(1). Listing a vertex’s neighbours is O(n), because you walk the whole row including every zero.

Which one

The social-network version of the question. If you only ever ask are these two people friends, one pair at a time, that’s the matrix. If you ask who is in this person’s network — friends, friends of friends, everything reachable — that’s the list.

The second is traversal, and traversal is what interviews ask for. The core move is “given a vertex, what are its neighbours,” once per vertex. On a list that sums to O(n + e) across a whole traversal. On a matrix it is O(n²), even if the graph has ten edges.

And sparsity settles it on its own, before any operation is named: n² is a cost the matrix charges just to exist. Ten thousand vertices and twenty thousand edges is a hundred million cells against thirty thousand entries.

Default to the adjacency list, defaultdict(list). Reach for the matrix only when the graph is dense and pair queries are the whole workload.

Directed or not

python

def add_edge(self, v, w):
    self.add_vertex(v)
    self.add_vertex(w)
    if w not in self.graph[v]:
        self.graph[v].append(w)
        # undirected: also append v to self.graph[w]

One line decides it, and getting it wrong is silent. An undirected add_edge used for dependencies means every task depends on every task it unblocks, so nothing ever has zero prerequisites and topological sort returns nothing.

2. One loop, three containers

BFS, DFS and uniform-cost search are the same algorithm. What changes is which item you take out of the frontier next.

python

def traverse(self, start):
    frontier = deque([start])
    seen = {start}
    while frontier:
        vertex = frontier.popleft()          # popleft → BFS · pop → DFS
        for neighbor in self.graph[vertex]:
            if neighbor not in seen:
                seen.add(neighbor)
                frontier.append(neighbor)
    return seen

Queue, take from the front → BFS. First in, first out, so everything at distance 1 is processed before anything at distance 2. Level by level, which is why it finds shortest paths in an unweighted graph.

Stack, take from the back → DFS. Most recent first, so you follow one branch to its end before backing up.

Heap, take the smallest → uniform-cost search, which on a graph is Dijkstra. Now the frontier holds (cost, vertex) and the cheapest route is explored first.

That is the whole distinction. Three algorithms taught separately, one loop with a different container.

Mark on push, not on pop

seen means already scheduled, not already processed. The add happens next to the append, not after the popleft.

If three vertices all point at x, marking on pop lets x be pushed three times before any of them is processed. The frontier fills with duplicates and the work multiplies. Marking on push means x enters the frontier exactly once, ever.

Which is also why seen is initialised with the start vertex: it was pushed.

The heap case, in outline

The third container is the one to know exists rather than to drill. Weighted shortest paths are off the required list this page is written against, and the unweighted cases carry the interview.

Three things that matter if it comes up.

The key is cumulative. The priority is the total cost from the start to that vertex, not the cost of the edge you just crossed.

python

heapq.heappush(frontier, (dist_so_far + edge_cost, neighbor))

Keyed on edge cost alone it is a greedy walk that looks right on small examples. Start → A costs 1, A → B costs 10, start → B costs 5: keyed on totals, B is reached at 5 while A’s route to B sits at 11. The two only diverge once the totals do.

seen becomes dist. A boolean set is not enough, because a vertex’s best-known distance improves after you have already reached it. Instead keep dist[v], the cheapest route found so far, and when a shorter one turns up, overwrite it and push again. That overwrite is what gets called relaxation: the edge is a constraint that starts violated and gets relaxed into satisfaction. Bad name, one-line operation.

Reconstructing the actual path needs a second dict, prev[v], naming the vertex you arrived from. Walk it backwards from the target.

It needs lazy deletion, for exactly the reason in dictionary compositions. The superseded entry is buried in the middle of the heap where it cannot be reached, so it stays and is discarded when it surfaces.

Same loop, same heap, different key, different algorithm:

Key	Algorithm	Gives you
`g(n)`, cost from the start	Dijkstra / UCS	shortest path, optimal
`h(n)`, estimated cost remaining	greedy best-first	fast, not optimal
`g(n) + h(n)`	A*	optimal if `h` never overestimates
cheapest edge leaving the built set	Prim’s	minimum spanning tree, not shortest paths

Dijkstra is A* with h = 0.

Recursive or iterative

BFS has no recursive form worth writing: recursion gives you a stack and BFS needs a queue.

DFS has both, and the recursive one is shorter, because the call stack is the stack:

python

def dfs(self, vertex, seen):
    if vertex in seen:
        return
    seen.add(vertex)
    for neighbor in self.graph[vertex]:
        self.dfs(neighbor, seen)

Python’s recursion limit is 1000, so a long path blows the stack on a graph in a way it rarely does on a tree — a balanced tree of a million nodes is only twenty deep. Name the limit out loud and write the recursive version anyway unless the interviewer pushes.

The real reason to prefer recursion: it gives you a natural place to act after all of a vertex’s neighbours are done, on the line following the loop. That is post-order, and it is awkward to reproduce with an explicit stack.

Which also answers why tree code is written recursively and graph code is written as a loop, when either form works for both. Two reasons, and neither is about elegance. Depth: a balanced tree of a million nodes is twenty levels deep, while a graph path can be as long as the vertex count, so recursion is safe on one and not the other. And bookkeeping: a tree has exactly one route to each node, so there is no seen set to carry, whereas a graph traversal is carrying explicit state anyway and the loop stops costing anything in clarity.

The dividing line that survives: recursion when you need to act on the way back up, a loop when you are only visiting.

3. Topological sort

Given tasks with dependencies, produce an order where every task comes after everything it depends on. compile after parse, link after compile.

This one has no start node, which is what makes it a different shape from everything above. BFS and UCS begin somewhere and explore outward. Here you begin with whatever is already unblocked, which might be several vertices or none at all.

The picture: every task carries a count of how many things must finish before it can start. Some are at zero, so they are ready now. Take a ready task, do it, and every task waiting on it is one dependency closer — decrement each of their counts. Any that hits zero just became ready. Repeat until nothing is ready.

In-degree

The count is the in-degree: how many arrows point at a vertex. An adjacency list gives you out-edges for free and in-edges nowhere, so compute them in one pass up front.

python

indeg = {v: 0 for v in self.graph}
for v in self.graph:
    for w in self.graph[v]:
        indeg[w] += 1

The dict comprehension seeds every vertex at zero first. Skip it and isolated vertices are missing from the counts entirely.

The counts get destroyed as the algorithm runs, which is fine for a one-shot sort. Maintaining a reverse adjacency list instead only pays off if in-degrees are queried repeatedly.

Kahn’s algorithm

python

def topological_sort(self):
    indeg = {v: 0 for v in self.graph}
    for v in self.graph:
        for w in self.graph[v]:
            indeg[w] += 1

    order = []
    ready = deque([v for v in indeg if indeg[v] == 0])
    while ready:
        vertex = ready.popleft()
        order.append(vertex)
        for neighbor in self.graph[vertex]:
            indeg[neighbor] -= 1
            if indeg[neighbor] == 0:
                ready.append(neighbor)

    return None if len(order) != len(self.graph) else order

ready holds vertices, not counts. indeg is the bookkeeping.

Push at the moment the count hits zero, inside the neighbour loop. The instinct to rebuild the ready set by rescanning indeg at the top of each iteration is both slower and wrong: every vertex already emitted still reads zero, so it comes straight back in and the loop never terminates. Emitting a vertex can only affect the vertices it points at, so nothing else needs re-examining.

== 0 rather than <= 0, so a vertex is pushed exactly once, on the transition.

A plain deque is correct because there is no priority. Any zero-in-degree vertex is equally valid to emit next, which is why the result is a valid order rather than the order. A heap only enters if the problem adds a tiebreak — run the alphabetically first ready task, or the shortest — and then nothing else changes.

Cycle detection comes free

If the ready set empties while vertices remain, those vertices are waiting on each other. len(order) != len(self.graph) is the check, and the missing vertices are exactly the cycle.

This is not a limitation being worked around. It is an equivalence, and the proof is short:

Every finite DAG has at least one vertex with in-degree zero. Suppose not — every vertex has an incoming edge. Start anywhere and walk backwards along incoming edges; you can always take another step. With finitely many vertices you must revisit one, and that repeat is a cycle.

So a DAG always has a starting point, and removing it leaves a DAG, which has another. Induction: the sort completes if and only if the graph is acyclic. Stalling early is proof a cycle exists, not a failure of the algorithm.

Returning a short list silently is the bug worth avoiding, since an empty result is otherwise indistinguishable from an empty graph.

4. Mistakes

Marking seen on pop instead of on push. Duplicates in the frontier, and the work multiplies on any vertex with several predecessors.
deque(start) instead of deque([start]). The constructor consumes an iterable, so a string start node becomes one entry per character.
Iterating the vertex instead of its neighbours. for n in vertex rather than for n in self.graph[vertex].
Adding the current vertex to seen inside the neighbour loop. It is already there; the neighbour is the one that needs marking.
An undirected add_edge used for a dependency graph. Nothing ever reaches in-degree zero and the sort returns nothing, with no error.
Rebuilding the ready set by rescanning in-degrees. Emitted vertices still read zero and re-enter forever.
Keying Dijkstra’s heap on edge cost rather than cumulative distance. Produces a greedy walk that looks right on small examples.