Graphs

How it works

A graph is anything made of things and connections: cities and roads, courses and prerequisites, grid cells and their neighbors, words one letter apart. The first step is always to see the graph, then pick a traversal.

Depth-first search explores one path to its end before backing up; it is natural for connected components, cycle detection and anything recursive. Breadth-first search expands in rings of equal distance, so the first time it reaches a node is by the fewest edges. Use BFS for shortest paths when every edge costs the same.

Every traversal needs a visited set, marked when a node is discovered rather than when it is processed, so nothing enters the queue twice. In a grid, the grid itself can serve as the visited marker.

Directed dependency problems ask for a topological order: repeatedly take nodes with no remaining prerequisites. If some nodes never reach zero, there is a cycle. Union-find answers 'are these connected?' incrementally as edges arrive.

How to attack it

1. 1Name the nodes and edges, and build an adjacency list if one is not given.
2. 2Decide the traversal: BFS for fewest steps, DFS for exploring or components.
3. 3Mark nodes visited when they are first pushed.
4. 4Start from every unvisited node if the graph may be disconnected.
5. 5For dependencies, use in-degrees and a queue (topological sort).

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

from collections import deque


def shortest_steps(graph, start, goal):
    # BFS: the first time we reach a node is by the fewest edges.
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            return dist[node]
        for nxt in graph[node]:
            if nxt not in dist:          # mark on discovery
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return -1


def topo_order(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for a, b in edges:                   # edge a -> b
        graph[a].append(b)
        indegree[b] += 1
    queue = deque(i for i in range(n) if indegree[i] == 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) == n else []   # [] means a cycle

What it costs