力扣刷题之815.公交路线

题干描述

给你一个数组 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

题干分析

问题描述

已知我们有这一系列的公交线路，以及routes数组，其中routes[i]表示dii来你个公交所进过的车站列表。每辆公交车按照起路线循环行驶。

目标：从起始站点source出发，前往目标站点target，且进通过乘坐公交车。
要求：找到从source到target需要乘坐的最少公交车数量。
注意：如果无法到达目标站点，返回-1。

示例：

输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：乘坐公交车 0 从站点 1 到站点 7，然后换乘公交车 1 到站点 6。

输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1
解释：无法从站点 15 到达站点 12。

解题思路

这个问题可以抽象为图的最短路径问题。我们需要构建一个公交车之间的图，然后使用官渡有限搜索（BFS）来找到从起始站点到目标站的最短路径。

节点（顶点）：公交车（每辆公交车做一个节点）。
边（连接）：若两辆公交车之间存在公共的站点，则它们之间可以换乘，形成一条边。
起始节点：所有进过source站点的公交车。
目标节点：所有经过target站点的公交车。
权重：每次换乘所一步，所以没条边的权重为1。

这里我们以示例2为例，大概如下：

步骤概述

1.建立站点到公交车的映射：

为每个站点创建一个列表，记录经过agic站点的所有公交车。

2.构建公交车之间的连接

对于没对公交车，如果它们有公共的站点，则它们之间可以直接换乘。

3.使用BFS进行搜索：

从所有经过source站点的公交车开始搜索。
逐层遍历可以换乘的公交车，记录乘坐的公交车数量。
如果某一辆公交车经过target站点，则返回已乘坐的公交车数量。

4.处理无法到达的情况：

如果在搜索结束后，仍未找到经过target站点的公交车，则返回-1。

代码讲解

#define MAX_BUS_STOPS 1000000
#define MAX_BUSES 500typedef struct {int bus_id;int next;
} BusNode;typedef struct {int head;
} BusStop;typedef struct {int bus_id;int depth;
} QueueNode;

第一步：定义数据结构

定义结构体BusNode：用于存储经过某个站点的公交车的链表节点，其中：

bus_id:用于定义公交车的编号。
next：用于指向下一个BusNode的索引。

定义结构体BusStop：表示一个公交站点，其中：

head：指向该站点对应的公交车链表的头节点索引。

定义结构体QueueNode：用于BFS队列，表示一个代访问的公交车节点。

bus_id：公交车的编号。
depth：到达该公交车所需乘坐的公交车数量。

第二步特殊情况考虑

如果source等于target，则无需乘坐公交车，直接返回0。

int numBusesToDestination(int** routes, int routesSize, int* routesColSize, int source, int target) {if (source == target) return 0;

第三步初始化站点到公交车的映射

创建一个大小为 MAX_BUS_STOPS 的数组 busStops，用于存储每个站点对应的公交车链表。
初始化每个站点的 head 为 -1，表示链表为空。

    // 创建站点到公交车的映射BusStop* busStops = (BusStop*)malloc(sizeof(BusStop) * MAX_BUS_STOPS);for (int i = 0; i < MAX_BUS_STOPS; i++) {busStops[i].head = -1;}

第四步初始化公交车链表数组

创建一个数组busNodes，用于存储所有的BusNode节点
busNodeCount用于记录已经使用的节点数量。

    for (int bus_id = 0; bus_id < routesSize; bus_id++) {for (int j = 0; j < routesColSize[bus_id]; j++) {int bus_stop_id = routes[bus_id][j];BusNode* node = &busNodes[busNodeCount++];node->bus_id = bus_id;node->next = busStops[bus_stop_id].head;busStops[bus_stop_id].head = busNodeCount - 1;}}

第五步建立站点到公交车的映射

遍历没来那个公交车的路线，将公交车编号添加到经过的每个站点的链表中。
对于每个站点，新的BusNode节点插入到链表头部。实现了链表的建立。

    // BFS 初始化int visitedBuses[MAX_BUSES];memset(visitedBuses, 0, sizeof(visitedBuses));int queueSize = MAX_BUSES * 1000;QueueNode* queue = (QueueNode*)malloc(sizeof(QueueNode) * queueSize);int front = 0, rear = 0;

第六步初始化 BFS所需的数据结构：

visiteBuses:记录已经访问过的公交车，防止重复访问。
queue：BFS队列，用于存储代访问的公交车。
front和rear：队列的头尾指针。

    // 将经过起始站点的公交车加入队列for (int idx = busStops[source].head; idx != -1; idx = busNodes[idx].next) {int bus_id = busNodes[idx].bus_id;if (!visitedBuses[bus_id]) {visitedBuses[bus_id] = 1;queue[rear++] = (QueueNode){bus_id, 1};}}

第七步将经过source站点的公交车加入队列

遍历source站点的公交车链表，将每个公交车编号加入队列，初始乘坐公交车数量为1。
标记这些公交车为已访问。

    // BFS 遍历while (front < rear) {QueueNode current = queue[front++];int bus_id = current.bus_id;int depth = current.depth;// 检查该公交车是否经过目标站点for (int i = 0; i < routesColSize[bus_id]; i++) {int bus_stop_id = routes[bus_id][i];if (bus_stop_id == target) {free(busStops);free(busNodes);free(queue);return depth;}}

第八步开始BFS遍历

从队列中取出一个公交车节点，湖区当前公交车编号和已乘坐的公交车数量。检查当前公交车是否经过target站点：

遍历该公交车的路线，如果发现target站点，返回当前乘坐的公交车数量depth。

第九步遍历当前公交车经过的所有站点

        // 将该公交车经过的所有站点的其他公交车加入队列for (int i = 0; i < routesColSize[bus_id]; i++) {int bus_stop_id = routes[bus_id][i];for (int idx = busStops[bus_stop_id].head; idx != -1; idx = busNodes[idx].next) {int next_bus_id = busNodes[idx].bus_id;if (!visitedBuses[next_bus_id]) {visitedBuses[next_bus_id] = 1;queue[rear++] = (QueueNode){next_bus_id, depth + 1};}}}}

对于当前公交车经过的每个站点