1.题目基本信息

1.1.题目描述

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

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

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

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

1.2.题目地址

https://leetcode.cn/problems/bus-routes/description/

2.解题方法

2.1.解题思路

思路：优化建图+广度优先搜索

时间复杂度：O(mn+n^2)（n为routes的长度，m为各个路线的平均长度）

2.2.解题步骤

第一步，建无向图。构建无向图graph，将各个路线看成图中的节点，如果两个路线具有相同的站点，则两个节点相连；并记录下起点站所在的路线的数组arr1和终点站所在的路线的集合set1

• 1.1.优化建图。使用map1维护"站点->[所在路线列表]"的映射，由于每个路线中的站点是不重复的，所以依次遍历所有路线中的所有站点，将当前遍历的路线route与map1[site]中所有的路线进行连接，即可得到正确的无向图

第二步，以arr1为起点，进行广度优先搜索，搜索到set1中路线就停止，此时搜索的深度即为最少乘坐的公交车数量

3.解题代码

python代码

from collections import defaultdict, deque

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        # 思路：优化建图+广度优先搜索
        # 时间复杂度：O(mn+n^2)（n为routes的长度，m为各个路线的平均长度）
        if source == target:
            return 0
        n = len(routes)
        # 第一步，建无向图。构建无向图graph，将各个路线看成图中的节点，如果两个路线具有相同的站点，则两个节点相连；并记录下起点站所在的路线的数组arr1和终点站所在的路线的集合set1
        arr1, set1 = [], set()
        # 1.1.优化建图。使用map1维护"站点->[所在路线列表]"的映射，由于每个路线中的站点是不重复的，所以依次遍历所有路线中的所有站点，将当前遍历的路线route与map1[site]中所有的路线进行连接，即可得到正确的无向图
        graph = [[] for _ in range(n)]
        map1 = defaultdict(list)
        for i in range(n):
            for site in routes[i]:
                for route in map1[site]:
                    graph[route].append(i)
                    graph[i].append(route)
                map1[site].append(i)
                if site == source:
                    arr1.append(i)
                if site == target:
                    set1.add(i)
        # print(graph)
        # print(arr1, set1)
        # 第二步，以arr1为起点，进行广度优先搜索，搜索到set1中路线就停止，此时搜索的深度即为最少乘坐的公交车数量
        visited = set(arr1)
        que = deque(arr1)
        steps = 0
        while que:
            steps += 1
            for _ in range(len(que)):
                node = que.popleft()
                if node in set1:
                    return steps
                for subNode in graph[node]:
                    if subNode not in visited:
                        que.append(subNode)
                        visited.add(subNode)
        return -1

4.执行结果