公交路线 图解题解

这道题到底在问什么

输入

routes=[[1,2,7],[3,6,7],[6,8,9]], source=1, target=9

输出

3(R0 → R1 → R2)

最优解：一步一步想明白

1. 3记住「建站→线路映射、再以线路为节点 BFS,层数就是乘车数」,下面逐帧套它。
2. 4先把 3 条线路各画成一个节点:R0=[1,2,7]、R1=[3,6,7]、R2=[6,8,9],此刻还没有任何边。下面逐站扫描,谁和谁共享站点,就在谁和谁之间连一条「可换乘」的边。
3. 5处理 R0 的站 1:把 R0 记到「站 1」名下。目前只有它一条线路经过这站,先记着。
4. 6处理 R0 的站 2:把 R0 记到「站 2」名下。目前只有它一条线路经过这站,先记着。
5. 7处理 R0 的站 7:把 R0 记到「站 7」名下。目前只有它一条线路经过这站,先记着。
6. 8处理 R1 的站 3:把 R1 记到「站 3」名下。目前只有它一条线路经过这站,先记着。
7. 9处理 R1 的站 6:把 R1 记到「站 6」名下。目前只有它一条线路经过这站,先记着。
8. 10线路 R1 经过站 7,而站 7 之前已经被 R0 记下了。这说明在站 7 可以从 R0 换乘到 R1,于是给 R0 和 R1 连一条边(高亮)。
9. 11线路 R2 经过站 6,而站 6 之前已经被 R1 记下了。这说明在站 6 可以从 R1 换乘到 R2,于是给 R1 和 R2 连一条边(高亮)。
10. 12处理 R2 的站 8:把 R2 记到「站 8」名下。目前只有它一条线路经过这站,先记着。
11. 13处理 R2 的站 9:把 R2 记到「站 9」名下。目前只有它一条线路经过这站,先记着。
12. 14映射建好了:站 7 把 R0、R1 连起来,站 6 把 R1、R2 连起来。现在这张「线路图」就成形了,接下来在它上面做 BFS,数从起点线路到含 target 的线路要走几步。
13. 15起点是站 1。先查映射:经过站 1 的线路是 R0,把它们入队、标记为已坐(乘车数从 1 起步)。BFS 第一层就是「坐第 1 辆车能到的线路」。
14. 16弹出队首 R0(紫色),它是坐第 1 辆车能到的线路之一。先看终点站 9 在不在它停靠的站里。
15. 17终点站 9 不在 R0 里。通过共享站换乘到新线路 R1(站 7),把它们入队、标记已坐。 R0 这条线路本轮处理完(变绿)。
16. 18第 1 辆车能到的线路都查完了,还没碰到终点。乘车数加到 2,继续处理队列里下一层的线路。
17. 19弹出队首 R1(紫色),它是坐第 2 辆车能到的线路之一。先看终点站 9 在不在它停靠的站里。
18. 20终点站 9 不在 R1 里。通过共享站换乘到新线路 R2(站 6),把它们入队、标记已坐。 R1 这条线路本轮处理完(变绿)。
19. 21第 2 辆车能到的线路都查完了,还没碰到终点。乘车数加到 3,继续处理队列里下一层的线路。
20. 22弹出队首 R2(紫色),它是坐第 3 辆车能到的线路之一。先看终点站 9 在不在它停靠的站里。
21. 23R2 停靠的站 [6,8,9] 里有终点站 9(变绿)!说明坐到第 3 辆车就能抵达,答案就是 3。BFS 第一次碰到含 target 的线路,层数即最少乘车数。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import defaultdict, deque
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()
        seen_routes = set()
        for r in stop_to_routes[source]:
            q.append(r)
            seen_routes.add(r)
        buses = 1
        while q:
            for _ in range(len(q)):
                r = q.popleft()
                if target in routes[r]:
                    return buses
                for stop in routes[r]:
                    for nr in stop_to_routes[stop]:
                        if nr not in seen_routes:
                            seen_routes.add(nr)
                            q.append(nr)
            buses += 1
        return -1

#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) return 0;
        unordered_map<int, vector<int>> stopToRoutes;
        for (int i = 0; i < (int)routes.size(); ++i) for (int stop : routes[i]) stopToRoutes[stop].push_back(i);
        queue<int> q;
        vector<int> seen(routes.size());
        for (int r : stopToRoutes[source]) { q.push(r); seen[r] = 1; }
        for (int buses = 1; !q.empty(); ++buses) {
            for (int sz = q.size(); sz--; ) {
                int r = q.front(); q.pop();
                for (int stop : routes[r]) {
                    if (stop == target) return buses;
                    for (int nr : stopToRoutes[stop]) if (!seen[nr]) {
                        seen[nr] = 1; q.push(nr);
                    }
                }
            }
        }
        return -1;
    }
};

import java.util.*;
class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;
        Map<Integer, List<Integer>> 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<Integer> q = new ArrayDeque<>();
        boolean[] seen = new boolean[routes.length];
        for (int r : stopToRoutes.getOrDefault(source, Collections.emptyList())) { q.offer(r); seen[r] = true; }
        for (int buses = 1; !q.isEmpty(); buses++) {
            for (int sz = q.size(); sz > 0; sz--) {
                int r = q.poll();
                for (int stop : routes[r]) {
                    if (stop == target) return buses;
                    for (int nr : stopToRoutes.get(stop)) if (!seen[nr]) {
                        seen[nr] = true; q.offer(nr);
                    }
                }
            }
        }
        return -1;
    }
}

复杂度

面试官可能追问