Graphs

When to reach for it

• Networks: friends, roads, services, build targets, config files that reference each other.
• Grids where you move between neighboring cells: islands, regions, mazes.
• Dependencies and ordering: prerequisites, build steps, issues that block other issues.
• The fewest steps (breadth-first search) or the cheapest path with weights (Dijkstra).
• Grouping connected items, especially as connections arrive over time (union-find).

The core idea

Build the graph explicitly first: a dictionary from each node to its neighbors. Then choose the traversal the question needs. Breadth-first search explores in rings of distance, so the first time it reaches a node is along a shortest path when every edge costs the same. Depth-first search goes deep first, which suits reachability, path finding and cycle detection. Both need a seen set so no node is processed twice.

Topological sort orders a directed graph without cycles so every edge points forward. Kahn's algorithm repeatedly takes a node with no remaining incoming edges; if some nodes are never taken, there is a cycle. Union-find keeps a parent pointer per node and merges groups in nearly constant time, which answers "are these two connected?" as edges keep arriving.

A Python template

from collections import defaultdict, deque

def build(edges, directed=False):
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        if not directed:
            graph[b].append(a)
    return graph

def fewest_steps(graph, start, goal):
    seen, queue = {start}, deque([(start, 0)])
    while queue:
        node, dist = queue.popleft()
        if node == goal:
            return dist
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)                 # mark when queued, not when popped
                queue.append((nxt, dist + 1))
    return -1                                 # unreachable

def dependency_order(nodes, edges):
    """edges are (before, after) pairs. Returns None if there is a cycle."""
    graph = build(edges, directed=True)
    waiting = {n: 0 for n in nodes}
    for _, after in edges:
        waiting[after] += 1
    ready = deque(n for n in nodes if waiting[n] == 0)
    order = []
    while ready:
        node = ready.popleft()
        order.append(node)
        for nxt in graph[node]:
            waiting[nxt] -= 1
            if waiting[nxt] == 0:
                ready.append(nxt)
    return order if len(order) == len(nodes) else None

Time and space

Breadth-first search, depth-first search and topological sort visit each node and edge once: O(V + E) time and O(V) space for the seen set and the queue or stack. Dijkstra with a heap is O((V + E) log V). Union-find with path compression and union by size is close to constant time per operation.

Common mistakes

• Marking a node as seen when it is popped instead of when it is queued, which queues it many times.
• Leaving out the seen set on a graph with cycles and looping forever.
• Using breadth-first search for shortest paths when edges have different weights.
• Adding edges in only one direction for an undirected graph.
• Not saying how a cycle is detected in a dependency graph, or what the function returns when there is one.

How to explain it out loud

Start by naming the graph: "Each build target is a node, and an edge goes from a target to everything that depends on it." Most graph mistakes come from a vague model, and saying it aloud lets Josh confirm or correct it before you have written anything.

Then name the algorithm and the reason for it: "I want the fewest steps and every step costs the same, so breadth-first search." Explain when nodes are marked as seen, give O(V + E), and say what happens with disconnected nodes or a cycle. That chain of reasoning is what Devana scores as approach planning and logic explanation.