Graph traversal and shortest paths

A graph is just a bunch of nodes connected by edges. Plenty of problems that never say "graph" are graph problems: cities and roads, tasks that depend on each other, cells in a grid.

BFS spreads out in rings from the start, so the first time it reaches a node, it took the fewest edges to get there. Dijkstra always goes to the cheapest node it knows about next, which works as long as no edge has a negative cost.

from collections import deque
import heapq


def bfs_distance(graph, start, goal):
    queue = deque([(start, 0)])
    seen = {start}
    while queue:
        node, distance = queue.popleft()
        if node == goal:
            return distance
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)
                queue.append((neighbour, distance + 1))
    return -1


def dijkstra(graph, start, goal):
    best = {start: 0}
    heap = [(0, start)]
    while heap:
        cost, node = heapq.heappop(heap)
        if node == goal:
            return cost
        if cost > best[node]:
            continue
        for neighbour, weight in graph[node]:
            next_cost = cost + weight
            if next_cost < best.get(neighbour, float("inf")):
                best[neighbour] = next_cost
                heapq.heappush(heap, (next_cost, neighbour))
    return -1

• Say what your nodes and edges are before you start coding.
• Ask if edges have costs or directions, and if there can be cycles.
• Be careful about tracking visited nodes, and give your complexity in terms of V and E.

Fewest moves on a grid with walls

You get a grid where '.' is open and '#' is a wall. Find the fewest moves from the top-left to the bottom-right, moving up, down, left or right. Return -1 if you can't get there.

1. Spot that it's a graph: each open cell is a node, and it has an edge to each open neighbor. Every move costs the same, so this is BFS.
2. Put the start cell on a queue with distance 0 and mark it seen.
3. Pop a cell. For each of its four neighbors that's inside the grid, open and not seen, mark it seen and push it with distance + 1.
4. Mark cells seen when you push them, not when you pop them. Otherwise the same cell can be added many times.
5. The first time you pop the goal, its distance is the answer, because BFS reaches everything at distance d before anything at d + 1.
6. If the queue empties first, return -1.
7. Each cell is pushed at most once and checks four neighbors, so it's O(rows × columns) time and space.

Things interviewers tend to ask once you've brought this up.

What if some cells cost more to enter?

Then fewest moves isn't cheapest path, so use Dijkstra. If costs are only 0 or 1, a deque where 0-cost moves go to the front works and is faster.

What if you can break through one wall?

Add it to the state: (row, column, walls broken). The same cell with and without a wall broken are different nodes.

How do you find an order for tasks with dependencies?

Topological sort. Count each task's incoming edges, start with the ones at zero, and remove edges as you go. If you can't finish, there's a cycle.

When would you use union find instead of BFS?

When edges keep arriving and you need to know if two things are connected after each one, like 'when did everyone become connected?'

• Marking nodes visited when you pop them instead of when you push them.
• Using DFS to find a shortest path.
• Using Dijkstra when there are negative costs.
• Forgetting the grid bounds or the visited set and looping forever.
• Not putting extra conditions, like keys collected or walls broken, into the state.

• Heaps and priority queuesAlways have the smallest or largest item ready.
• Dynamic programmingSolve each subproblem once and reuse the answer.
• Binary searchCut the search in half, even when you're searching for an answer.