结对

public List getStationsBetween(String startStation, String endStation, List<List> allSubwayStations) {
List stationsBetween = new ArrayList<>();
Map<String, List> graph = buildGraph(allSubwayStations);

    // 检查起始站和终点站是否存在于地铁网络中
    if (!graph.containsKey(startStation) || !graph.containsKey(endStation)) {
        System.out.println("起始站或终点站不在地铁网络中");
        return stationsBetween;
    }
    
    // 使用BFS搜索起始站到终点站之间的所有站点
    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    Map<String, String> parentMap = new HashMap<>();
    
    queue.offer(startStation);
    visited.add(startStation);
    
    while (!queue.isEmpty()) {
        String currentStation = queue.poll();
        if (currentStation.equals(endStation)) {
            // 找到终点站，构建站点路径并返回
            String station = endStation;
            while (!station.equals(startStation)) {
                stationsBetween.add(station);
                station = parentMap.get(station);
            }
            stationsBetween.add(startStation);
            Collections.reverse(stationsBetween);
            return stationsBetween;
        }
        
        List<String> neighbors = graph.get(currentStation);
        if (neighbors != null) {
            for (String neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                    parentMap.put(neighbor, currentStation);
                }
            }
        }
    }
    
    // 如果没有找到路径，返回空列表
    System.out.println("无法找到起始站到终点站之间的路径");
    return stationsBetween;
}

// 构建地铁站点图
private Map<String, List<String>> buildGraph(List<List<String>> allSubwayStations) {
    Map<String, List<String>> graph = new HashMap<>();
    for (List<String> lineStations : allSubwayStations) {
        for (int i = 0; i < lineStations.size(); i++) {
            String station = lineStations.get(i);
            if (!graph.containsKey(station)) {
                graph.put(station, new ArrayList<>());
            }
            if (i > 0) {
                String prevStation = lineStations.get(i - 1);
                graph.get(station).add(prevStation);
                graph.get(prevStation).add(station);
            }
        }
    }
    return graph;
}