Graphs

Modelling comes first

Most graph questions do not say "graph". They say courses with prerequisites, words one edit apart, a grid of land and water, packages that depend on packages. The work is deciding what a node is and what an edge means; once that is settled, the algorithm is usually BFS or DFS off the shelf.

Two representations, and the choice is about density:

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"]}   # adjacency list — default
matrix = [[0, 1, 1], [0, 0, 1], [0, 0, 0]]                # adjacency matrix — dense, O(1) edge test

A list is O(V + E) space and makes traversal linear. A matrix is O(V²) space and only pays off when the graph is dense or you need to ask "is there an edge between these two" constantly.

The two traversals are one algorithm

def traverse(graph, source):
    seen = {source}
    frontier = deque([source])           # stack -> DFS, queue -> BFS
    while frontier:
        node = frontier.popleft()        # .pop() for DFS
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)            # mark on discovery, not on expansion
                frontier.append(nxt)

Swap the container and the order of exploration changes completely; everything else is identical. Two details in that loop carry all the weight:

• seen is checked before queuing. Without it, a cycle makes the loop run forever.
• Nodes are marked when discovered, not when expanded. Mark on expansion and a node can sit in the queue several times over.

BFS and shortest paths

Because BFS drains the queue in distance order, nodes come out in layers: everything one edge away, then everything two edges away. The first time a node is discovered is therefore along a path with the fewest edges — the guarantee that makes BFS the answer to "minimum number of steps".

def shortest_path(graph, source, target):
    parent = {source: None}
    queue = deque([source])
    while queue:
        node = queue.popleft()
        if node == target:
            break
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node        # remember how we got here
                queue.append(nxt)
    path, node = [], target               # walk the parents backwards
    while node is not None:
        path.append(node)
        node = parent.get(node)
    return path[::-1]

Storing a parent alongside each node is what turns "how far" into "which route". The moment edges carry different weights, this argument collapses and you need Dijkstra — the same loop with a heap as the frontier.

DFS and structure

Depth-first is the tool for questions about structure rather than distance: cycles, components, ordering, articulation points. The recursive form is short enough to write under pressure, but remember the stack depth is the path length — an explicit stack is safer on large graphs.

Topological order, via Kahn's algorithm:

def topo(graph, indegree):
    queue = deque(n for n in graph if indegree[n] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == len(graph) else []    # short = cycle

That last line is two answers in one: the ordering when it exists, and cycle detection when it does not.

Which algorithm

What to say in the interview

State the model first — "nodes are cells, edges are the four neighbours" — then name the traversal and why. Give the cost as O(V + E) and say what V and E are in this problem, because for a grid that is rows × cols and four times that. If the question mentions weights, say why BFS is no longer sufficient before reaching for a heap.

Possible follow-up questions