Bus Routes

Bus Routes is a graph problem in disguise. The trick is realizing that the routes — not the stops — are the nodes you want to search over. Once you see that, it becomes a plain shortest-path BFS.

The slow way first

You might BFS over stops, treating each stop as a node. That works, but a single bus connects every pair of stops on its route, so you re-walk the same route's stops over and over and the edge count explodes. Worse, counting "buses taken" gets awkward when your nodes are stops, not buses.

The question to ask: what am I actually choosing each step? You are choosing which bus to board next. So make the buses themselves the nodes.

The idea: routes are nodes, shared stops are edges

Build a graph where each route is a node. Two routes are connected if they share a stop — that shared stop is exactly where you can transfer between them. Then BFS from the routes serving source: the BFS depth at which you first reach a route that covers target is the fewest buses.

The key insight: BFS explores ring by ring, so the first time we reach a route covering the target, we have used the fewest buses possible.

Walk through it

Step through the animation. Each circle is a route. We start at R0 (it serves the source stop 1) with the bus count at 1. We pop R0, see it does not cover stop 9, and expand through shared stop 7 to R1 — that is bus 2. We keep going: R1 to R2 via stop 6 (bus 3), R2 to R3 via stop 8 (bus 4). When we pop R3 it contains stop 9, so we return 4.

Pseudocode

build map stop_to_routes: each stop -> list of routes serving it
queue <- every route serving source, each tagged with bus count 1
mark those routes as seen
while queue not empty:
    (route, buses) <- pop front
    if target is one of this route's stops:
        return buses                 # first time = fewest buses
    for each stop on this route:
        for each neighbor route serving that stop:
            if neighbor not seen:
                mark seen, push (neighbor, buses + 1)
return -1                            # target unreachable

The Python solution

def num_buses(routes, source, target):
    stop_to_routes = defaultdict(list)
    for r, stops in enumerate(routes):
        for s in stops:
            stop_to_routes[s].append(r)
    queue = deque()
    seen = set()
    for r in stop_to_routes[source]:
        queue.append((r, 1)); seen.add(r)
    while queue:
        route, buses = queue.popleft()
        if target in routes[route]:
            return buses
        for s in routes[route]:
            for nxt in stop_to_routes[s]:
                if nxt not in seen:
                    seen.add(nxt); queue.append((nxt, buses + 1))
    return -1

• stop_to_routes maps a stop → the routes that serve it, so we can find transfers in O(1).
• We seed the queue with every route that serves source, each tagged with a bus count of 1.
• seen holds the routes already queued, so we never board the same bus twice.
• When we pop a route, we first check target in routes[route] — if found, the bus count is the answer because BFS reaches it at minimal depth.
• To expand, we look at each stop on the current route and queue every unseen neighbor route with buses + 1.

Complexity

Let N be the number of routes and S the total count of stops across them. The map build is O(S), and the BFS touches each route and its stops once, so the whole thing is O(S) time and space. The win comes from searching over the small set of routes instead of re-expanding stops.

When this pattern shows up

Practice