Graph

Representation

An adjacency list maps each node to its neighbours — O(V+E) space, fast to iterate edges. An adjacency matrix is a V×V grid — O(V^2) space but O(1) edge lookup. Lists win for sparse graphs (most real ones).

Cities and roads

Cities are nodes, roads are edges. One-way roads are a directed graph; toll costs are edge weights.

Build & traverse

A dict of lists is enough. BFS finds shortest paths in unweighted graphs; DFS explores components and cycles.

from collections import defaultdict, deque
g = defaultdict(list)
for u, v in edges:
    g[u].append(v)
    g[v].append(u)   # undirected

def bfs(start):
    seen, q = {start}, deque([start])
    while q:
        node = q.popleft()
        for nb in g[node]:
            if nb not in seen:
                seen.add(nb)
                q.append(nb)
    return seen

Algorithm menu

Unweighted shortest path → BFS. Weighted, non-negative → Dijkstra. Ordering with dependencies → topological sort. Connectivity groups → Union-Find or DFS.