bfs典型题-公交线路

本文针对一个典型的 bfs 问题进行分析。

在处理 leetcode 815.公交路线[https://leetcode-cn.com/problems/bus-routes/] 题目时，使用 bfs 方法进行解答，结果发现超出时间限制。答案中也提供了 bfs 的处理方案，却在时间限制之内，针对这个奇怪的问题，这里进行分析。

仔细读题，可以发现，题目中给了两个量，一个是 站点，另一个为 路线（routes）。（感觉 routes 结构比较类似 邻接表，存储结点之间的连接关系）。路线放置在一个二维数组中，routes[][]。每条线路 routes[i] 中，放置该线路经过的站点值。数据的规模规定如下：

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

在 bfs 的时候，实际上有两个选择，可以以 站点 为目标，进行遍历，也可以以 路线 为目标进行遍历。代码分别如下：

/**
以 站点 为对象 进行 bfs
*/
public int numBusesToDestination1(int[][] routes, int source, int target) {
    if(source == target) return 0;

    // map 保存每个 站点 被哪些公交路线所经过
    Map<Integer, List<Integer>> map = new HashMap<>();
    // passedStops: 记录经过的站点值，以及抵达该站点需要乘坐的公交线路数量
    Map<Integer, Integer> passedStops = new HashMap<>();
    // deque: bfs 使用的结构，里面放置待遍历的站点值
    Deque<Integer> deque = new ArrayDeque<>();

    // 初始化
    passedStops.put(source, 0);
    deque.add(source);
    for(int i = 0; i < routes.length; ++i){
        for(int j = 0; j < routes[i].length; ++j){
            List<Integer> passedRoutes = map.getOrDefault(routes[i][j], new ArrayList<Integer>());
            passedRoutes.add(i);
            map.put(routes[i][j], passedRoutes);
        }
    }
    if(map.get(source) == null) return -1;

    // bfs
    while(!deque.isEmpty()){
        int stop = deque.poll();
        // currentDis 记录当前站点距离 起点的距离
        int currentDis = passedStops.get(stop);
        // passedRoutes: 为经过该站点所有路线
        List<Integer> passedRoutes = map.get(stop);
        // 遍历经过该站点的所有路线
        for(Integer route : passedRoutes){
            for(int tmpStop : routes[route]){
                if(!passedStops.containsKey(tmpStop)){
                    if(tmpStop == target) return currentDis + 1;
                    passedStops.put(tmpStop, currentDis + 1);
                    deque.add(tmpStop);
                }
            }
        }
    }
    return -1;
}

/**
以 路线 为对象进行 bfs
*/
public int numBusesToDestination2(int[][] routes, int source, int target) {
    if(source == target) return 0;

    // map 保存每个 站点 被哪些公交路线所经过
    Map<Integer, List<Integer>> map = new HashMap<>();
    // taken 保存公交线路访问的情况，key 值为已经乘坐的公交线路的下表，routes[i], value 为乘坐该线路需要经过的总线路数（包含当前线路）
    Map<Integer, Integer> taken = new HashMap<>();
    // deque: bfs 使用的队列，其中放置经过的路线值
    Deque<Integer> deque = new ArrayDeque<>();

    // 初始化
    for(int i = 0; i < routes.length; ++i){
        for(int j = 0; j < routes[i].length; ++j){
            // 如果线路经过 source 站点，说明这个线路可以为起始线路，放入 deque 中，等待遍历。
            // 此外，标记该线路为 taken，乘坐的线路数为 1
            if(routes[i][j] == source){
                deque.offer(i);
                taken.put(i, 1);
            }
            // 更新站点到 路线直线的映射信息
            List<Integer> passedRoutes = map.getOrDefault(routes[i][j], new ArrayList<Integer>());
            passedRoutes.add(i);
            map.put(routes[i][j], passedRoutes);
        }
    }

    // bfs
    while(!deque.isEmpty()){
        int routeNumber = deque.poll();
        int currentRoutesNumbers = taken.get(routeNumber);
        // 遍历 该路线 经过的站点
        for(int stop : routes[routeNumber]){
            if(stop == target) return currentRoutesNumbers;
            // 获取经过该站点的 路线列表
            List<Integer> passedRoutes = map.get(stop);
            if(passedRoutes == null) continue;
            for(Integer route : passedRoutes){
                // 随着遍历的深入，currentRoutesNumbers 一定是递增的。因此，只要更新 taken 中还不存在的 route
                if(!taken.containsKey(route)){
                    taken.put(route, currentRoutesNumbers + 1);
                    deque.add(route);
                }
            }
        }
    }
    return -1;
}

差别分析：设站点的数量为 n, 路线的数量为 m。以站点为对象进行分析的时候， deque 的最大长度应该是 站点的数量，而每一次 while(!deque.isEmpty()) 中，是从 站点 -> 经过站点的路线 -> 路线经过的站点进行遍历，复杂度 为 O(m*n)，因此总的复杂度为 O(n^2*m)。而针对路线进行分析，deque 的最大长度为 路线的数量， while(!deque.isEmpty()) 中，是从 路线 -> 该路线经过的站点 -> 经过该站点的路径 的过程进行遍历， 因此算法的时间复杂度为 O(n*m^2)。由于题目中声明，站点的数量规模 sum(routes[i].length) <= 10^5，而路线的数量规模仅仅为 1 <= routes.length <= 500，因此，在所有数据规模都为上限的情况下，以路线为对象进行 bfs，复杂度要远远低于以 站点为对象进行 bfs。