企业官网建设流程全解析

瑞安网站建设步骤,织梦网站怎样入侵,wordpress会员插件,公众号怎么制作合集更高效的公交最少乘车次数规划#xff1a;基于邻接矩阵 广度优先搜索的优化算法摘要#xff1a;日常公交出行规划中#xff0c;“最少换乘#xff08;最少乘车次数#xff09;” 是用户最核心的需求之一。传统的全量遍历 BFS 算法在路线数量较多时效率偏低#xff0c;本…更高效的公交最少乘车次数规划基于邻接矩阵 广度优先搜索的优化算法摘要日常公交出行规划中“最少换乘最少乘车次数” 是用户最核心的需求之一。传统的全量遍历 BFS 算法在路线数量较多时效率偏低本文基于 “邻接矩阵 哈希表预处理” 的思路优化了公交路线间的换乘关系存储方式结合广度优先搜索BFS实现了更高效的最少乘车次数计算。一、为什么要优化之前我们组写过一个 “全量遍历” 的公交最少换乘算法核心是每次搜索都遍历所有路线判断能不能换乘。这个思路虽然好懂但有个问题 ——路线多了就变慢。比如一个城市有 100 条公交线每次找换乘路线都要遍历 100 条反复做 “检查两条路线有没有公共站点” 的操作相当于做了大量重复计算。就像你查公交时每找一次换乘都要把所有线路翻一遍效率肯定高不了。那能不能换个思路提前把所有路线之间的换乘关系记下来比如用一张 “路线换乘表”想知道路线 A 和路线 B 能不能换乘直接查表就行不用每次都去比对站点。这就是本文算法的核心 —— 先预处理再搜索把 “重复劳动” 提前做完让搜索过程更高效。二、核心思路先 “建表”再 “搜路”整个算法可以分成两大步预处理阶段用哈希表记录 “每个站点对应哪些路线”用邻接矩阵记录 “哪些路线之间可以换乘”—— 相当于提前建好两张关键的表BFS 搜索阶段以 “路线” 为节点利用建好的邻接矩阵逐层搜索能到达终点的路线找到最少乘车次数。这个思路的本质是用预处理的时间换搜索的时间尤其适合需要多次查询的场景比如同一个公交网络查不同起点终点。三、先搞懂几个关键 “工具”在看代码之前先把算法里用到的核心数据结构和概念说清楚不然容易看懵。3.1 哈希表unordered_map快速找 “经过某站的所有路线”哈希表的特点是 “键值对存储查询速度快”这里我们用它存键站点编号比如 1、5、7值经过这个站点的所有路线编号比如经过站点 5 的路线有 0、2、3。举个例子rec[5] [0,2,3]意思是 “站点 5 被路线 0、路线 2、路线 3 经过”。有了这个表想知道 “哪些路线能到起点 S”直接查rec[S]就行不用遍历所有路线这是第一个优化点。3.2 邻接矩阵快速判断 “两条路线能不能换乘”邻接矩阵是一个二维数组edgeedge[i][j] true表示 “路线 i 和路线 j 可以换乘”false则表示不能。比如有 3 条路线邻接矩阵可能长这样路线0120否是否1是否是2否是否意思是路线 0 和 1 能换乘路线 1 和 2 能换乘路线 0 和 2 不能换乘。有了这个矩阵判断两条路线能不能换乘只需要查一下矩阵的值不用再遍历站点比对这是第二个优化点。3.3 距离数组dis记录 “坐几条线能到这条路线”dis数组的下标是路线编号值是 “从起点出发最少坐几条线能到这条路线”。比如dis[2] 3意思是 “从起点到路线 2最少需要坐 3 条公交线换乘 2 次”。初始时dis数组全设为 - 1表示没访问过只有经过起点的路线dis值设为 1坐 1 条线就能到。四、代码逻辑拆解一步步看懂接下来我们把代码掰开揉碎从预处理到搜索每一步都讲清楚。4.1 第一步特殊情况处理 —— 起点就是终点如果输入的起点 S 和终点 T 是同一个站直接返回 0不用查任何路线这是最基础的优化。if (S T) {return 0;}4.2 第二步预处理 1—— 构建哈希表和邻接矩阵这是整个算法最核心的预处理步骤目的是建好 “站点 - 路线” 表和 “路线 - 换乘” 表。1初始化数据结构int n routes.size(); // 总路线数// 邻接矩阵n行n列初始全为false不能换乘vectorvectorbool edge(n, vectorbool(n, false));// 哈希表键站点值经过该站点的路线列表unordered_mapint, vectorint rec;2遍历所有路线填充哈希表和邻接矩阵for (int i 0; i n; i) { // 遍历第i条路线for (int stop : routes[i]) { // 遍历第i条路线的每个站点// 关键如果这个站点之前被其他路线经过过说明这些路线和当前路线i能换乘for (int j : rec[stop]) {edge[i][j] edge[j][i] true; // 标记i和j可换乘双向}// 把当前路线i加入这个站点的路线列表rec[stop].push_back(i);}}举个例子帮你理解先处理路线 0站点是 [1,3,5]站点 1rec 里没有直接把路线 0 加入 rec [1]站点 3rec 里没有直接把路线 0 加入 rec [3]站点 5rec 里没有直接把路线 0 加入 rec [5]再处理路线 1站点是 [5,7,9]站点 5rec 里有路线 0所以标记 edge [1][0] edge [0][1] true然后把路线 1 加入 rec [5]站点 7rec 里没有加入 rec [7]站点 9rec 里没有加入 rec [9]。这样一来我们就知道路线 0 和 1 能换乘因为都经过站点 5邻接矩阵里对应的位置就变成了 true。4.3 第三步预处理 2—— 初始化 BFS 队列和距离数组vectorint dis(n, -1); // 距离数组初始-1未访问queueint que; // BFS队列存路线编号// 把所有经过起点S的路线加入队列作为BFS的起点for (int bus : rec[S]) {dis[bus] 1; // 坐1条线就能到这条路线que.push(bus);}比如起点 S 是 1rec [1] [0]那么 dis [0] 1队列里加入 0。4.4 第四步BFS 核心搜索 —— 找最少乘车次数这一步的逻辑很简单从经过起点的路线出发逐层找能换乘的路线记录每条路线的最少乘车次数。while (!que.empty()) { // 队列不为空就继续int x que.front(); // 取出队首的路线xque.pop(); // 弹出队首for (int y 0; y n; y) { // 遍历所有路线y// 条件1路线x和y能换乘条件2路线y没被访问过if (edge[x][y] dis[y] -1) {dis[y] dis[x] 1; // 乘车次数1que.push(y); // 把y加入队列继续搜索}}}还是举例子队列里初始是路线 0dis [0]1取出路线 0遍历所有路线 yy1edge [0][1]truedis [1]-1 → dis [1] 112加入队列其他路线edge [0][y]false跳过接下来处理队列里的路线 1继续找能换乘的路线……4.5 第五步计算最终结果 —— 找到达终点的最少乘车次数int ret INT_MAX; // 初始设为最大整数// 遍历所有经过终点T的路线for (int bus : rec[T]) {if (dis[bus] ! -1) { // 这条路线能到达ret min(ret, dis[bus]); // 取最小值}}// 没找到就返回-1否则返回最少乘车次数return ret INT_MAX ? -1 : ret;比如终点 T 是 9rec [9] [1]dis [1]2 → 最少乘车次数就是 2换乘 1 次。4.6 辅助函数手动输入路线和站点这部分代码很简单就是让用户输入路线数量、每条路线的站点数和站点编号最终返回一个二维数组routes比如routes [[1,3,5],[5,7,9]]。4.7 主函数整合所有步骤主函数的逻辑就是调用inputRoutes()让用户输入路线输入起点 S 和终点 T调用numBusesToDestination()计算最少乘车次数输出结果。下面是全部代码更高效的公交最少乘车次数规划基于邻接矩阵 广度优先搜索的优化算法摘要日常公交出行规划中“最少换乘最少乘车次数” 是用户最核心的需求之一。传统的全量遍历 BFS 算法在路线数量较多时效率偏低本文基于 “邻接矩阵 哈希表预处理” 的思路优化了公交路线间的换乘关系存储方式结合广度优先搜索BFS实现了更高效的最少乘车次数计算。一、为什么要优化聊聊传统算法的痛点之前我们组写过一个 “全量遍历” 的公交最少换乘算法核心是每次搜索都遍历所有路线判断能不能换乘。这个思路虽然好懂但有个致命问题 ——路线多了就变慢。比如一个城市有 100 条公交线每次找换乘路线都要遍历 100 条反复做 “检查两条路线有没有公共站点” 的操作相当于做了大量重复计算。就像你查公交时每找一次换乘都要把所有线路翻一遍效率肯定高不了。那能不能换个思路提前把所有路线之间的换乘关系记下来比如用一张 “路线换乘表”想知道路线 A 和路线 B 能不能换乘直接查表就行不用每次都去比对站点。这就是本文算法的核心 —— 先预处理再搜索把 “重复劳动” 提前做完让搜索过程更高效。二、核心思路先 “建表”再 “搜路”整个算法可以分成两大步预处理阶段用哈希表记录 “每个站点对应哪些路线”用邻接矩阵记录 “哪些路线之间可以换乘”—— 相当于提前建好两张关键的表BFS 搜索阶段以 “路线” 为节点利用建好的邻接矩阵逐层搜索能到达终点的路线找到最少乘车次数。这个思路的本质是用预处理的时间换搜索的时间尤其适合需要多次查询的场景比如同一个公交网络查不同起点终点。三、先搞懂几个关键 “工具”在看代码之前先把算法里用到的核心数据结构和概念说清楚不然容易看懵。3.1 哈希表unordered_map快速找 “经过某站的所有路线”哈希表的特点是 “键值对存储查询速度快”这里我们用它存键站点编号比如 1、5、7值经过这个站点的所有路线编号比如经过站点 5 的路线有 0、2、3。举个例子rec[5] [0,2,3]意思是 “站点 5 被路线 0、路线 2、路线 3 经过”。有了这个表想知道 “哪些路线能到起点 S”直接查rec[S]就行不用遍历所有路线这是第一个优化点。3.2 邻接矩阵快速判断 “两条路线能不能换乘”邻接矩阵是一个二维数组edgeedge[i][j] true表示 “路线 i 和路线 j 可以换乘”false则表示不能。比如有 3 条路线邻接矩阵可能长这样路线0120否是否1是否是2否是否意思是路线 0 和 1 能换乘路线 1 和 2 能换乘路线 0 和 2 不能换乘。有了这个矩阵判断两条路线能不能换乘只需要查一下矩阵的值不用再遍历站点比对这是第二个优化点。3.3 距离数组dis记录 “坐几条线能到这条路线”dis数组的下标是路线编号值是 “从起点出发最少坐几条线能到这条路线”。比如dis[2] 3意思是 “从起点到路线 2最少需要坐 3 条公交线换乘 2 次”。初始时dis数组全设为 - 1表示没访问过只有经过起点的路线dis值设为 1坐 1 条线就能到。四、代码逻辑拆解一步步看懂接下来我们把代码掰开揉碎从预处理到搜索每一步都讲清楚。4.1 第一步特殊情况处理 —— 起点就是终点如果输入的起点 S 和终点 T 是同一个站直接返回 0不用查任何路线这是最基础的优化。if (S T) {return 0;}4.2 第二步预处理 1—— 构建哈希表和邻接矩阵这是整个算法最核心的预处理步骤目的是建好 “站点 - 路线” 表和 “路线 - 换乘” 表。1初始化数据结构int n routes.size(); // 总路线数// 邻接矩阵n行n列初始全为false不能换乘vectorvectorbool edge(n, vectorbool(n, false));// 哈希表键站点值经过该站点的路线列表unordered_mapint, vectorint rec;2遍历所有路线填充哈希表和邻接矩阵for (int i 0; i n; i) { // 遍历第i条路线for (int stop : routes[i]) { // 遍历第i条路线的每个站点// 关键如果这个站点之前被其他路线经过过说明这些路线和当前路线i能换乘for (int j : rec[stop]) {edge[i][j] edge[j][i] true; // 标记i和j可换乘双向}// 把当前路线i加入这个站点的路线列表rec[stop].push_back(i);}}举个例子帮你理解先处理路线 0站点是 [1,3,5]站点 1rec 里没有直接把路线 0 加入 rec [1]站点 3rec 里没有直接把路线 0 加入 rec [3]站点 5rec 里没有直接把路线 0 加入 rec [5]再处理路线 1站点是 [5,7,9]站点 5rec 里有路线 0所以标记 edge [1][0] edge [0][1] true然后把路线 1 加入 rec [5]站点 7rec 里没有加入 rec [7]站点 9rec 里没有加入 rec [9]。这样一来我们就知道路线 0 和 1 能换乘因为都经过站点 5邻接矩阵里对应的位置就变成了 true。4.3 第三步预处理 2—— 初始化 BFS 队列和距离数组vectorint dis(n, -1); // 距离数组初始-1未访问queueint que; // BFS队列存路线编号// 把所有经过起点S的路线加入队列作为BFS的起点for (int bus : rec[S]) {dis[bus] 1; // 坐1条线就能到这条路线que.push(bus);}比如起点 S 是 1rec [1] [0]那么 dis [0] 1队列里加入 0。4.4 第四步BFS 核心搜索 —— 找最少乘车次数这一步的逻辑很简单从经过起点的路线出发逐层找能换乘的路线记录每条路线的最少乘车次数。while (!que.empty()) { // 队列不为空就继续int x que.front(); // 取出队首的路线xque.pop(); // 弹出队首for (int y 0; y n; y) { // 遍历所有路线y// 条件1路线x和y能换乘条件2路线y没被访问过if (edge[x][y] dis[y] -1) {dis[y] dis[x] 1; // 乘车次数1que.push(y); // 把y加入队列继续搜索}}}还是举例子队列里初始是路线 0dis [0]1取出路线 0遍历所有路线 yy1edge [0][1]truedis [1]-1 → dis [1] 112加入队列其他路线edge [0][y]false跳过接下来处理队列里的路线 1继续找能换乘的路线……4.5 第五步计算最终结果 —— 找到达终点的最少乘车次数int ret INT_MAX; // 初始设为最大整数// 遍历所有经过终点T的路线for (int bus : rec[T]) {if (dis[bus] ! -1) { // 这条路线能到达ret min(ret, dis[bus]); // 取最小值}}// 没找到就返回-1否则返回最少乘车次数return ret INT_MAX ? -1 : ret;比如终点 T 是 9rec [9] [1]dis [1]2 → 最少乘车次数就是 2换乘 1 次。4.6 辅助函数手动输入路线和站点这部分代码很简单就是让用户输入路线数量、每条路线的站点数和站点编号最终返回一个二维数组routes比如routes [[1,3,5],[5,7,9]]。4.7 主函数整合所有步骤主函数的逻辑就是调用inputRoutes()让用户输入路线输入起点 S 和终点 T调用numBusesToDestination()计算最少乘车次数输出结果。五、举个完整例子算法怎么跑用一个具体的例子把整个流程走一遍你就全懂了。输入路线数量2路线 1索引 01 3 5路线 2索引 15 7 9起点 S1终点 T9执行过程特殊情况S≠T继续预处理哈希表和邻接矩阵rec[1] [0]rec[3] [0]rec[5] [0,1]rec[7] [1]rec[9] [1]edge[0][1] edge[1][0] true初始化 BFSrec [S1] [0] → dis [0] 1队列加入 0BFS 搜索取出队列里的 0遍历 y0 到 1y1edge [0][1]truedis [1]-1 → dis [1] 2队列加入 1计算结果rec[T9] [1]dis[1]2 → ret2输出最少需要乘坐 2 辆公交车换乘 1 次。六、优化点对比为什么这个算法更快和之前的全量遍历算法比这个优化版本的核心优势在两个地方对比项传统全量遍历算法邻接矩阵 哈希表优化算法找经过站点的路线遍历所有路线逐个检查站点哈希表直接查O (1) 级别的速度判断两条路线能否换乘遍历站点比对重复计算邻接矩阵直接查O (1) 级别的速度整体效率O (n²*m)n 路线数m 站点数O (n² 总站点数)简单说传统算法是 “用到了再算”优化算法是 “提前算好用到了直接查”路线越多优化效果越明显。七、算法的优缺点和改进方向7.1 优点效率高预处理后搜索过程几乎没有重复计算适合路线多的场景逻辑清晰预处理 搜索的两步走分工明确容易理解实用性强哈希表和邻接矩阵都是常用数据结构代码容易落地。7.2 缺点空间开销邻接矩阵的空间复杂度是 O (n²)如果路线数 n 特别大比如 1000 条矩阵会占用较多内存只算次数不返回路线这个算法只能算出最少坐几条线但没法返回具体的路线顺序比如路线 0→路线 1如果需要输出路线还得在 BFS 里记录路径不考虑站点数和之前的算法一样只关注乘车次数不考虑总坐多少站。7.3 改进方向优化空间把邻接矩阵换成邻接表比如vectorvectorint adj只存能换乘的路线节省内存记录具体路线在 BFS 时用一个数组prev记录每条路线的上一条路线最后回溯出完整的路线序列多目标优化加入站点数的权重比如 “乘车次数 ×2 总站点数”用加权 BFS 找综合最优解。八、总结这篇文章讲的算法核心是 “提前预处理减少重复计算”—— 用哈希表快速定位 “站点对应的路线”用邻接矩阵快速判断 “路线能否换乘”再结合 BFS 的逐层搜索高效找到最少乘车次数。相比于传统的全量遍历算法这个优化版本在路线数量较多时优势明显而且逻辑并不复杂只要理解了 “哈希表存站点 - 路线”“邻接矩阵存路线 - 换乘” 这两个核心点就能轻松上手。五、举个完整例子算法怎么跑用一个具体的例子把整个流程走一遍你就全懂了。输入路线数量2路线 1索引 01 3 5路线 2索引 15 7 9起点 S1终点 T9执行过程特殊情况S≠T继续预处理哈希表和邻接矩阵rec[1] [0]rec[3] [0]rec[5] [0,1]rec[7] [1]rec[9] [1]edge[0][1] edge[1][0] true初始化 BFSrec [S1] [0] → dis [0] 1队列加入 0BFS 搜索取出队列里的 0遍历 y0 到 1y1edge [0][1]truedis [1]-1 → dis [1] 2队列加入 1计算结果rec[T9] [1]dis[1]2 → ret2输出最少需要乘坐 2 辆公交车换乘 1 次。六、优化点对比为什么这个算法更快和之前的全量遍历算法比这个优化版本的核心优势在两个地方对比项传统全量遍历算法邻接矩阵 哈希表优化算法找经过站点的路线遍历所有路线逐个检查站点哈希表直接查O (1) 级别的速度判断两条路线能否换乘遍历站点比对重复计算邻接矩阵直接查O (1) 级别的速度整体效率O (n²*m)n 路线数m 站点数O (n² 总站点数)简单说传统算法是 “用到了再算”优化算法是 “提前算好用到了直接查”路线越多优化效果越明显。七、算法的优缺点和改进方向7.1 优点效率高预处理后搜索过程几乎没有重复计算适合路线多的场景逻辑清晰预处理 搜索的两步走分工明确容易理解实用性强哈希表和邻接矩阵都是常用数据结构代码容易落地。7.2 缺点空间开销邻接矩阵的空间复杂度是 O (n²)如果路线数 n 特别大比如 1000 条矩阵会占用较多内存只算次数不返回路线这个算法只能算出最少坐几条线但没法返回具体的路线顺序比如路线 0→路线 1如果需要输出路线还得在 BFS 里记录路径不考虑站点数和之前的算法一样只关注乘车次数不考虑总坐多少站。7.3 改进方向优化空间把邻接矩阵换成邻接表比如vectorvectorint adj只存能换乘的路线节省内存记录具体路线在 BFS 时用一个数组prev记录每条路线的上一条路线最后回溯出完整的路线序列多目标优化加入站点数的权重比如 “乘车次数 ×2 总站点数”用加权 BFS 找综合最优解。八、总结这篇文章讲的算法核心是 “提前预处理减少重复计算”—— 用哈希表快速定位 “站点对应的路线”用邻接矩阵快速判断 “路线能否换乘”再结合 BFS 的逐层搜索高效找到最少乘车次数。相比于传统的全量遍历算法这个优化版本在路线数量较多时优势明显而且逻辑并不复杂只要理解了 “哈希表存站点 - 路线”“邻接矩阵存路线 - 换乘” 这两个核心点就能轻松上手。