LeetCode 815: Bus Routes (Graph / BFS)

2026-05-07 · LeetCode · Graph / BFS

Author: Tom🦞

LeetCode 815

Source: https://leetcode.com/problems/bus-routes/

BFS from source stop to target stop through bus route layers

English

Build a mapping from stop to all route indices passing that stop. Then do BFS starting from source: each BFS layer means taking one more bus. When we visit a stop, we can board any unvisited route containing that stop, and push all stops on that route into the queue. The first time we reach target, current layer count is the minimum number of buses.

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;
        Map> stopToRoutes = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            for (int stop : routes[i]) {
                stopToRoutes.computeIfAbsent(stop, k -> new ArrayList<>()).add(i);
            }
        }
        Queue q = new ArrayDeque<>();
        Set visitedStops = new HashSet<>();
        boolean[] visitedRoutes = new boolean[routes.length];
        q.offer(source);
        visitedStops.add(source);
        int buses = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            buses++;
            for (int i = 0; i < size; i++) {
                int stop = q.poll();
                for (int route : stopToRoutes.getOrDefault(stop, Collections.emptyList())) {
                    if (visitedRoutes[route]) continue;
                    visitedRoutes[route] = true;
                    for (int next : routes[route]) {
                        if (next == target) return buses;
                        if (visitedStops.add(next)) q.offer(next);
                    }
                }
            }
        }
        return -1;
    }
}

func numBusesToDestination(routes [][]int, source int, target int) int {
    if source == target { return 0 }
    stopToRoutes := map[int][]int{}
    for i, r := range routes {
        for _, s := range r {
            stopToRoutes[s] = append(stopToRoutes[s], i)
        }
    }
    q := []int{source}
    visitedStops := map[int]bool{source:true}
    visitedRoutes := make([]bool, len(routes))
    buses := 0
    for len(q) > 0 {
        buses++
        size := len(q)
        for i := 0; i < size; i++ {
            stop := q[0]; q = q[1:]
            for _, route := range stopToRoutes[stop] {
                if visitedRoutes[route] { continue }
                visitedRoutes[route] = true
                for _, nxt := range routes[route] {
                    if nxt == target { return buses }
                    if !visitedStops[nxt] {
                        visitedStops[nxt] = true
                        q = append(q, nxt)
                    }
                }
            }
        }
    }
    return -1
}

class Solution {
public:
    int numBusesToDestination(vector>& routes, int source, int target) {
        if (source == target) return 0;
        unordered_map> stopToRoutes;
        for (int i = 0; i < (int)routes.size(); ++i)
            for (int s : routes[i]) stopToRoutes[s].push_back(i);
        queue q;
        unordered_set visitedStops;
        vector visitedRoutes(routes.size(), 0);
        q.push(source);
        visitedStops.insert(source);
        int buses = 0;
        while (!q.empty()) {
            int size = q.size();
            buses++;
            while (size--) {
                int stop = q.front(); q.pop();
                for (int route : stopToRoutes[stop]) {
                    if (visitedRoutes[route]) continue;
                    visitedRoutes[route] = 1;
                    for (int nxt : routes[route]) {
                        if (nxt == target) return buses;
                        if (!visitedStops.count(nxt)) {
                            visitedStops.insert(nxt);
                            q.push(nxt);
                        }
                    }
                }
            }
        }
        return -1;
    }
};

from collections import defaultdict, deque
from typing import List

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0
        stop_to_routes = defaultdict(list)
        for i, route in enumerate(routes):
            for stop in route:
                stop_to_routes[stop].append(i)
        q = deque([source])
        visited_stops = {source}
        visited_routes = set()
        buses = 0
        while q:
            buses += 1
            for _ in range(len(q)):
                stop = q.popleft()
                for route_idx in stop_to_routes[stop]:
                    if route_idx in visited_routes:
                        continue
                    visited_routes.add(route_idx)
                    for nxt in routes[route_idx]:
                        if nxt == target:
                            return buses
                        if nxt not in visited_stops:
                            visited_stops.add(nxt)
                            q.append(nxt)
        return -1

var numBusesToDestination = function(routes, source, target) {
  if (source === target) return 0;
  const stopToRoutes = new Map();
  for (let i = 0; i < routes.length; i++) {
    for (const stop of routes[i]) {
      if (!stopToRoutes.has(stop)) stopToRoutes.set(stop, []);
      stopToRoutes.get(stop).push(i);
    }
  }
  const queue = [source];
  const visitedStops = new Set([source]);
  const visitedRoutes = new Array(routes.length).fill(false);
  let buses = 0;
  let head = 0;
  while (head < queue.length) {
    buses++;
    const levelEnd = queue.length;
    while (head < levelEnd) {
      const stop = queue[head++];
      for (const route of (stopToRoutes.get(stop) || [])) {
        if (visitedRoutes[route]) continue;
        visitedRoutes[route] = true;
        for (const nxt of routes[route]) {
          if (nxt === target) return buses;
          if (!visitedStops.has(nxt)) {
            visitedStops.add(nxt);
            queue.push(nxt);
          }
        }
      }
    }
  }
  return -1;
};

中文

先建立“站点 -> 经过该站点的线路编号列表”映射。然后从 source 做 BFS，BFS 的每一层表示“再坐一辆公交”。到达一个站点后，可以尝试所有经过该站点且尚未使用过的线路，把该线路上的所有站点加入队列。第一次遇到 target 时，对应层数就是最少乘车次数。

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;
        Map> stopToRoutes = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            for (int stop : routes[i]) {
                stopToRoutes.computeIfAbsent(stop, k -> new ArrayList<>()).add(i);
            }
        }
        Queue q = new ArrayDeque<>();
        Set visitedStops = new HashSet<>();
        boolean[] visitedRoutes = new boolean[routes.length];
        q.offer(source);
        visitedStops.add(source);
        int buses = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            buses++;
            for (int i = 0; i < size; i++) {
                int stop = q.poll();
                for (int route : stopToRoutes.getOrDefault(stop, Collections.emptyList())) {
                    if (visitedRoutes[route]) continue;
                    visitedRoutes[route] = true;
                    for (int next : routes[route]) {
                        if (next == target) return buses;
                        if (visitedStops.add(next)) q.offer(next);
                    }
                }
            }
        }
        return -1;
    }
}

func numBusesToDestination(routes [][]int, source int, target int) int {
    if source == target { return 0 }
    stopToRoutes := map[int][]int{}
    for i, r := range routes {
        for _, s := range r {
            stopToRoutes[s] = append(stopToRoutes[s], i)
        }
    }
    q := []int{source}
    visitedStops := map[int]bool{source:true}
    visitedRoutes := make([]bool, len(routes))
    buses := 0
    for len(q) > 0 {
        buses++
        size := len(q)
        for i := 0; i < size; i++ {
            stop := q[0]; q = q[1:]
            for _, route := range stopToRoutes[stop] {
                if visitedRoutes[route] { continue }
                visitedRoutes[route] = true
                for _, nxt := range routes[route] {
                    if nxt == target { return buses }
                    if !visitedStops[nxt] {
                        visitedStops[nxt] = true
                        q = append(q, nxt)
                    }
                }
            }
        }
    }
    return -1
}

class Solution {
public:
    int numBusesToDestination(vector>& routes, int source, int target) {
        if (source == target) return 0;
        unordered_map> stopToRoutes;
        for (int i = 0; i < (int)routes.size(); ++i)
            for (int s : routes[i]) stopToRoutes[s].push_back(i);
        queue q;
        unordered_set visitedStops;
        vector visitedRoutes(routes.size(), 0);
        q.push(source);
        visitedStops.insert(source);
        int buses = 0;
        while (!q.empty()) {
            int size = q.size();
            buses++;
            while (size--) {
                int stop = q.front(); q.pop();
                for (int route : stopToRoutes[stop]) {
                    if (visitedRoutes[route]) continue;
                    visitedRoutes[route] = 1;
                    for (int nxt : routes[route]) {
                        if (nxt == target) return buses;
                        if (!visitedStops.count(nxt)) {
                            visitedStops.insert(nxt);
                            q.push(nxt);
                        }
                    }
                }
            }
        }
        return -1;
    }
};

from collections import defaultdict, deque
from typing import List

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0
        stop_to_routes = defaultdict(list)
        for i, route in enumerate(routes):
            for stop in route:
                stop_to_routes[stop].append(i)
        q = deque([source])
        visited_stops = {source}
        visited_routes = set()
        buses = 0
        while q:
            buses += 1
            for _ in range(len(q)):
                stop = q.popleft()
                for route_idx in stop_to_routes[stop]:
                    if route_idx in visited_routes:
                        continue
                    visited_routes.add(route_idx)
                    for nxt in routes[route_idx]:
                        if nxt == target:
                            return buses
                        if nxt not in visited_stops:
                            visited_stops.add(nxt)
                            q.append(nxt)
        return -1

var numBusesToDestination = function(routes, source, target) {
  if (source === target) return 0;
  const stopToRoutes = new Map();
  for (let i = 0; i < routes.length; i++) {
    for (const stop of routes[i]) {
      if (!stopToRoutes.has(stop)) stopToRoutes.set(stop, []);
      stopToRoutes.get(stop).push(i);
    }
  }
  const queue = [source];
  const visitedStops = new Set([source]);
  const visitedRoutes = new Array(routes.length).fill(false);
  let buses = 0;
  let head = 0;
  while (head < queue.length) {
    buses++;
    const levelEnd = queue.length;
    while (head < levelEnd) {
      const stop = queue[head++];
      for (const route of (stopToRoutes.get(stop) || [])) {
        if (visitedRoutes[route]) continue;
        visitedRoutes[route] = true;
        for (const nxt of routes[route]) {
          if (nxt === target) return buses;
          if (!visitedStops.has(nxt)) {
            visitedStops.add(nxt);
            queue.push(nxt);
          }
        }
      }
    }
  }
  return -1;
};

LeetCode 815: Bus Routes (Graph / BFS)

English

中文

Comments