公交路线

难度: Hard

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。

现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

示例 1：

输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。

示例 2：

输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1

提示：

1 <= routes.length <= 500.
1 <= routes[i].length <= 10⁵
routes[i] 中的所有值 互不相同
sum(routes[i].length) <= 10⁵
0 <= routes[i][j] < 10⁶
0 <= source, target < 10⁶

Submission

运行时间: 116 ms

内存: 40.6 MB

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0
        num = len(routes)
        transpose = collections.defaultdict(list)
        for idx , route in enumerate(routes):
            for state in route:
                # 站点： 交通车路线
                transpose[state].append(idx) 
                
        queue = []
        visited = set()
        visited.add(source)
        visited_bus = set()
        for start in transpose[source]:
            # 交通车路线
            queue.append((start, 0))
            visited_bus.add(start)


        while len(queue)>0:
            node, value = queue.pop(0)
            for neighbour_state in routes[node]:
                if neighbour_state == target:
                    return value + 1
                if neighbour_state not in visited:
                    visited.add(neighbour_state)
                    for start in transpose[neighbour_state]:
                        if start not in visited_bus:
                            queue.append((start, value + 1))
                            visited_bus.add(start)
        return -1

Explain

该题解采用了宽度优先搜索（BFS）的策略。首先，使用一个字典 transpose 将站点和公交路线进行映射，键为站点，值为经过该站点的所有公交路线的索引。接着，从源站点出发，使用队列进行层序遍历，每一层代表乘坐一次公交车。遍历过程中，记录已访问的站点和已乘坐的公交路线，以避免重复访问。当到达目标站点时，返回当前的乘坐次数。

时间复杂度: O(S * R)

空间复杂度: O(S * R)

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0
        num = len(routes)
        transpose = collections.defaultdict(list)
        for idx , route in enumerate(routes):
            for state in route:
                transpose[state].append(idx) 
        
        queue = []
        visited = set()
        visited.add(source)
        visited_bus = set()
        for start in transpose[source]:
            queue.append((start, 0))
            visited_bus.add(start)

        while len(queue)>0:
            node, value = queue.pop(0)
            for neighbour_state in routes[node]:
                if neighbour_state == target:
                    return value + 1
                if neighbour_state not in visited:
                    visited.add(neighbour_state)
                    for start in transpose[neighbour_state]:
                        if start not in visited_bus:
                            queue.append((start, value + 1))
                            visited_bus.add(start)
        return -1

Explore

宽度优先搜索（BFS）是解决此类问题的理想选择，因为它可以保证在找到目标站点时已经使用的公交车次数是最少的。BFS通过逐层探索所有可能的路径直到找到目标，这对于最短路径问题非常适合。而深度优先搜索（DFS）可能会深入探索某一条路径而忽略了更短的替代路径，因此它不适合用于寻找最少次数的问题。

使用站点作为键，公交路线索引作为值的方式构建`transpose`字典有利于快速查找任何站点可直接乘坐的所有公交路线。这种映射结构使得在宽度优先搜索过程中可以迅速确定从当前站点可以直接到达的其他站点，从而有效地遍历和转换乘车线路。此外，这种结构还有助于避免重复检查已乘坐的公交线路，因为我们可以直接通过站点查询相关的公交路线，从而优化搜索效率。

在BFS中，每次从队列中取出一个元素（即当前公交路线以及已乘坐的次数），我们会检查通过当前路线可以到达的所有站点。如果其中包含目标站点，则直接返回当前乘坐次数加一。如果不包含目标站点，则将从当前站点可达的、尚未访问过的站点加入队列，同时更新已访问站点和已乘坐路线的记录。这种方法确保每次扩展都是在尝试最少的乘坐次数的情况下进行，因此可以保证找到的第一个符合条件的结果就是乘坐次数最少的解。

在本算法实现中，通过维护一个已访问站点集合`visited`来处理循环路线。每次访问一个站点前，会检查该站点是否已经被访问过。如果已经访问过，则不会再次对该站点进行操作，从而避免了进入循环路线导致的无限循环问题。这种方法有效地避免了重复访问同一站点，从而处理了可能的循环路线问题。