前言

本周学习的内容很纯粹：

  1. 图论 相关
  2. 动态规划 基础
  3. C++ Stllib
    因为只是学完了图论，但是DP还没学完，所以这周就先总结图论吧，DP留到下周在讲。

图论

现在对于图论有了一个基本认识，知道了如何建图，以及特殊建图方式：“链式前向星”。
学习了拓扑序，最小生成树的概念（以及两种求最小生成树的算法：KruskarAlgo 和 primAlgo，
以及基本的图遍历BFS和双向BFS，单源最短路算法 DijkstraAlgo，并了解了分层图最短路，
最后学习了四种图相关基本算法：A*、Floyd、Bellman-Floyd、SPFA。
整理一下就是：

  1. 图的建立、链式前向星 -> 2025-03-31
  2. 拓扑序 -> 2025-03-31
  3. 最小生成树 -> 2025-04-01
  4. BFS -> 2025-04-01
  5. 双向BFS -> 2025-04-02
  6. Dijkstra算法、分层路最短图 -> 2025-04-02
  7. A*、Floyd、Bellman-Floyd、SPFA -> 2025-04-02

对于图而言，模板很重要，啃下模板是基础的基础。
在此之上，会有对题目的额外理解，每个题目独有的设计和对应推理过程，
不过那应该是较困难的内容了，对于入门者而言，先把模板背熟才是上策。
然后就是挑选合适模板，总之，对于笔试or比赛而言，A了就是胜利。
时空复杂度低的模板往往没这么考验码力，总之量力而为，一切以A题为准。
至于对题目设计的独有推理，则应该需要长期的刷题刷出“手感”
所以加油吧，认清自己的“入门者”身份，然后不懈努力。

碎碎念：

链式前向星

第一次接触觉得很高大上啊，这个名字。
深入了解之后只佩服名字太贴切了！
“链式”暗示了“算法对边的组织”，“前向”暗示了 “边是出边”，
“星”则很详细的展示了每一个单元的拓扑形象 - 像一个放射边的星。

拓扑序

第一次接触这个概念还是在软件工程的 里程碑问题 中接触到的，
拓扑序揭示了 有向无环图 中的某些依赖关系特征。

双向BFS

双向BFS更像是一个技巧，
无论是用于折半样本遍历样本解空间，还是头尾相向搜索，
实际上都是对整个解空间的大剪枝。

图、图的建立与链式前向星

图

一般来说，图的种类有：

  1. 有向 vs 无向
  2. 不带权 vs 带权
    在实际题目中，
    入参一般为： 节点数量n和所有的边 或者 直接给图。

图的建立

建图的三种方式，我们图解一下！

  1. 邻接矩阵（适合点的数量不多的图）
  2. 邻接表（最常用的方式）
  3. 链式前向星（空间要求严苛情况下使用。比赛必用，大厂笔试、面试不常用）

什么是链式前向星？

链式前向星 是一种用静态数组 模拟 链表跳转的结构，
可以比其他两种方式更节省内存。
其精髓在于对 边 编号，每个节点只保留所连接的 头边 信息，
再通过维护 next数组 构建跳转信息，
其中还要维护 to数组 保存每条边的去向节点信息。
这样就可以像 邻接表 一样查询了。

拓扑序

什么是拓扑序/拓扑排序？

要求：有向图、没有环；
即只有在有向无环图中才存在拓扑序。

拓扑排序的顺序可能不只一种。拓扑排序也可以用来判断有没有环。
1）在图中找到所有入度为0的点
2）把所有入度为0的点在图中删掉，重点是删掉影响！继续找到入度为0的点并删掉影响
3）直到所有点都被删掉，依次删除的顺序就是正确的拓扑排序结果
4）如果无法把所有的点都删掉，说明有向图里有环

重要技巧：
利用拓扑排序的过程，上游节点逐渐推送消息给下游节点的技巧，
这个技巧已经是树型DP的内容了，可以稍微领略一下树形DP。

例题分析

题目1

拓扑排序模版
邻接表建图（动态方式）
测试链接 : https://leetcode.cn/problems/course-schedule-ii

链式前向星建图（静态方式）
测试链接 : https://www.nowcoder.com/practice/88f7e156ca7d43a1a535f619cd3f495c

题目2

字典序最小的拓扑排序
测试链接 : https://www.luogu.com.cn/problem/U107394

1
要求返回所有正确的拓扑排序中 字典序最小 的结果

注意：解决该问题需要使用小根堆，建图请使用链式前向星方式，因为比赛平台用其他建图方式会卡空间

题目3

火星词典
测试链接 : https://leetcode.cn/problems/alien-dictionary

1
2
3
4
5
6
7
8
现有一种使用英语字母的火星语言
这门语言的字母顺序对你来说是未知的。
给你一个来自这种外星语言字典的字符串列表 words
words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
如果这种说法是错误的，并且给出的 words 不能对应任何字母的顺序，则返回 ""
否则，返回一个按新语言规则的 字典递增顺序 排序的独特字符串
如果有多个解决方案，则返回其中任意一个
words中的单词一定都是小写英文字母组成的

实际上就是构建字母的拓扑序。
关键在于找到第一个不同的字母，然后获取字典序大小（依赖）关系。
其中需要注意判断一下是否矛盾，如果矛盾要直接返回空串。

题目4

戳印序列
测试链接 : https://leetcode.cn/problems/stamping-the-sequence

1
2
3
4
5
6
7
8
9
10
你想最终得到"abcbc"，认为初始序列为"?????"。印章是"abc"
那么可以先用印章盖出"??abc"的状态，
然后用印章最左字符和序列的0位置对齐，就盖出了"abcbc"
这个过程中，"??abc"中的a字符，被印章中的c字符覆盖了
每次盖章的时候，印章必须完全盖在序列内
给定一个字符串target是最终的目标，长度为n，认为初始序列为n个'?'
给定一个印章字符串stamp，目标是最终盖出target，但是印章的使用次数必须在10*n次以内
返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成
上面的例子返回[2,0]，表示印章最左字符依次和序列2位置、序列0位置对齐盖下去，就得到了target
如果不能在10*n次内印出序列，就返回一个空数组

很难想的题目啊！实际上解题关键在于：后盖的会覆盖前面盖的，
也就是说，遍历的去盖对于 target 上每一个位置上的字母，如果他是正确的，那么他就应该在那里。
如果他不正确，那么可能将来某一次盖章会覆盖掉这个错误，然后我们就可以因此找到这个依赖关系，而有了依赖关系我们就可以构建有向无环图，拿到拓扑序，也就是题解。

题目5

最大食物链计数
测试链接 : https://www.luogu.com.cn/problem/P4017

1
2
3
a -> b，代表a在食物链中被b捕食
给定一个有向无环图，返回
这个图中从最初级动物到最顶级捕食者的食物链有几条

标准的通过拓扑序过程推送信息的题。

题目6

喧闹和富有
测试链接 : https://leetcode.cn/problems/loud-and-rich/

1
2
3
4
5
6
7
8
9
10
从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值
给你一个数组richer，其中richer[i] = [ai, bi] 表示 
person ai 比 person bi 更有钱
还有一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值
richer 中所给出的数据 逻辑自洽
也就是说，在 person x 比 person y 更有钱的同时，不会出现
person y 比 person x 更有钱的情况
现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是,
在所有拥有的钱 肯定不少于 person x 的人中，
person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。

在这里我们要注意，

  1. 构建从有钱为源头指向没钱的有向无环图。
  2. 拓扑序过程推送的信息是来自 上游 中更安静的那一个（即假如有多个上游，取最值）。

题目7

并行课程 III
测试链接 : https://leetcode.cn/problems/parallel-courses-iii/

1
2
3
4
5
6
7
8
9
10
给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n
同时给你一个二维整数数组 relations ，
其中 relations[j] = [prevCoursej, nextCoursej]
表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）
同时给你一个下标从 0 开始的整数数组 time
其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。
请你根据以下规则算出完成所有课程所需要的 最少 月份数：
如果一门课的所有先修课都已经完成，你可以在 任意 时间开始这门课程。
你可以 同时 上 任意门课程 。请你返回完成所有课程所需要的 最少 月份数。
注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）

经典软件工程中的里程碑问题，实际上和上一题一致，只不过推送的信息改为了先修时间，每个节点的最大修行时间取决于 上游 的最大值。

题目8

参加会议的最多员工数
测试链接 : https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/

1
2
3
4
5
6
一个公司准备组织一场会议，邀请名单上有 n 位员工
公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工
员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工
每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议
每位员工喜欢的员工 不会 是他自己。给你一个下标从 0 开始的整数数组 favorite
其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目

好抽象的题。
通过分析，可以得出两种情况

  1. 可能性1 : 所有小环(中心个数 == 2)，算上中心点 + 延伸点，总个数
  2. 可能性2 : 所有大环(中心个数 > 2)，只算中心点，最大环的中心点个数
    答案取两种情况的最值。
    拓扑序主要在这里起到剥离链找到环的作用，并且通过推送技巧可以把环上每一个节点所链接的最长链的长度记录上。

最小生成树（MST）

最小生成树（Minimum Spanning Tree, MST） 是图论中的一个重要概念，通常用于优化网络连接问题。
定义：在一个连通无向图中，连接所有顶点的最小权重的树。
特点：
1. 包含所有顶点：MST包含图中的所有顶点。
2. 无环（Acyclic）：MST是一棵树，不包含任何环。
3. 最小权重（Minimum Weight）：MST的边权和最小。
最小生成树可能不只一棵，只要保证边的总权值最小，就都是正确的最小生成树
如果无向带权图有n个点，那么最小生成树一定有n-1条边

扩展：最小生成树一定是最小瓶颈树

最小瓶颈生成树（MBST）

最小瓶颈生成树（MBST）是最小生成树（MST）的一个变种，侧重于最小化树中最大权重的边。
目标：在所有连接整个图的生成树（Spanning Tree）中，使得最大的边权最小。
区别：MST 关注的是所有边权之和最小，而 MBST 关注的是最重边的权值最小。

最小瓶颈生成树不一定是唯一的，但所有MBST的最大边权是相同的。
所有的MST都是MBST（但MBST不一定是MST）。
MST的最大权重边就是MBST的最大权重边（因为MST已经是所有可能树中最优的）。

MST求解 - Kruskal算法（最常用）

  1. 把所有的边，根据权值从小到大排序，从权值小的边开始考虑
  2. 如果连接当前的边不会形成环，就选择当前的边
  3. 如果连接当前的边会形成环，就不要当前的边
  4. 考察完所有边之后，最小生成树的也就得到了

    时间复杂度O(m * log m) + O(n) + O(m)
    最简单，不用多少脑子，利用并查集实现。

MST求解 - Prim算法（不算常用）

  1. 解锁的点的集合叫set（普通集合）、解锁的边的集合叫heap（小根堆）。set和heap都为空。
  2. 可从任意点开始，开始点加入到set，开始点的所有边加入到heap
  3. 从heap中弹出权值最小的边e，查看边e所去往的点x:
    1. 如果x已经在set中，边e舍弃，重复步骤3
    2. 如果x不在set中，边e属于最小生成树，把x加入set，重复步骤3
  4. 当heap为空，最小生成树的也就得到了

    时间复杂度O(n + m) + O(m * log m)
    从代码实现以及算法时空复杂度考虑，未优化的版本基本上都劣于 Kruskal算法。

Prim算法的优化（比较难）

  1. 小根堆里放(节点，到达节点的花费)，根据 到达节点的花费 来组织小根堆
  2. 小根堆弹出(u节点，到达u节点的花费y)，y累加到总权重上去，然后考察u出发的每一条边, 假设，u出发的边，去往v节点，权重w
    1. 如果v已经弹出过了（发现过），忽略该边
    2. 如果v从来没有进入过堆，向堆里加入记录(v, w)
    3. 如果v在堆里，且记录为(v, x)
      1. 如果w < x，则记录更新成(v, w)，然后调整该记录在堆中的位置（维持小根堆）
      2. 如果w >= x，忽略该边
  3. 重复 步骤2，直到小根堆为空

    时间复杂度O(n+m) + O((m+n) * log n)
    优化之后，复杂度取决于节点数量，所以更适用于稠密图。

例题分析：

题目1

返回最小生成树的最小权值和
测试链接 : https://www.luogu.com.cn/problem/P3366

最小生成树（MST） 模板题。

题目2

水资源分配优化
测试链接 : https://leetcode.cn/problems/optimize-water-distribution-in-a-village/

1
2
3
4
5
6
7
村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。
对于每个房子 i，我们有两种可选的供水方案：一种是直接在房子内建造水井
成本为 wells[i - 1] （注意 -1 ，因为 索引从0开始 ）
另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，
其中每个 pipes[j] = [house1j, house2j, costj] 
代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。
请返回 为所有房子都供水的最低总成本

可以假定有一个水源，然后水源可以通向每一个村庄，这些路的代价就是每个村庄打井的代价，然后求 最小生成树（MST） 即可。

题目3

检查边长度限制的路径是否存在
测试链接 : https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/

1
2
3
4
5
6
7
8
给你一个 n 个点组成的无向图边集 edgeList
其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边
请注意，两个点之间可能有 超过一条边 。
给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj]
你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径
且这条路径上的每一条边都 严格小于 limitj 。
请你返回一个 布尔数组 answer ，其中 answer.length == queries.length
当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false

实际上就是求一个符合规则的 最小生成树（MST），然后再检测这个树中是否包含这两个节点。

题目4

繁忙的都市
测试链接 : https://www.luogu.com.cn/problem/P2330

1
2
3
4
5
6
7
8
9
10
11
一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造
城市的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连
两个交叉路口之间最多有一条道路相连接，这些道路是双向的
且把所有的交叉路口直接或间接的连接起来了
每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造
但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来
2. 在满足要求1的情况下，改造的道路尽量少
3. 在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小
作为市规划局的你，应当作出最佳的决策，选择哪些道路应当被修建
返回选出了几条道路 以及 分值最大的那条道路的分值是多少

最小生成树（MST） 一定同时也是 最小瓶颈树（MBST）。
所以，题目就是让你求 最小生成树（MST）。

广度优先搜索（BFS）

广度优先搜索（Breadth-First Search, BFS）

是一种用于遍历或搜索图（Graph）或树（Tree）的算法。它按照层级（Level Order）逐层向外扩展，优先访问当前层的所有节点，然后再访问下一层的节点。
BFS 适用于：

  • 最短路径问题（无权图/网格）
  • 连通性检查
  • 状态搜索问题（如棋类游戏的最优解、最少转换次数等）

bfs的特点是逐层扩散，从源头点到目标点扩散了几层，最短路就是多少
bfs可以使用的特征是 任意两个节点之间的相互距离相同（无向图）
bfs开始时，可以是 单个源头、也可以是 多个源头
bfs频繁使用队列，形式可以是 单点弹出 或者 整层弹出
bfs进行时，进入队列的节点需要标记状态，防止 同一个节点重复进出队列
bfs进行时，可能会包含 剪枝策略 的设计
bfs是一个理解难度很低的算法，难点在于 节点如何找到路、路的展开 和 剪枝设计

01BFS

01bfs，适用于 图中所有边的权重只有0和1两种值，求源点到目标点的最短距离
时间复杂度为 O(节点数量+边的数量)

  1. distance[i]表示从源点到i点的最短距离，初始时所有点的distance设置为无穷大
  2. 源点进入双端队列，distance[源点]=0
  3. 双端队列 头部弹出 x，
    1. 如果x是目标点，返回 distance[x] 表示源点到目标点的最短距离
    2. 考察从x出发的每一条边，假设某边去y点，边权为w
      1. 如果 distance[y] > distance[x] + w，处理该边；否则忽略该边
      2. 处理时，更新 distance[y] = distance[x] + w
        如果w == 0，y从头部进入双端队列；如果w == 1，y从尾部进入双端队列
      3. 考察完x出发的所有边之后，重复步骤3
  4. 双端队列为空停止

    为什么不能用 传统BFS ？- 因为点与点的权不是一样的，
    可以理解为传统BFS适用图的权都是0。
    为什么不需要 Visited数组 标记？ - 因为进队的节点要不就是下一层节点，
    要不就是同层节点（边权 1 或者 边权 0）就算前面的点对后面的点发生修正，也最多修正一次，而且流程中会忽略掉该修正后的点， distance数组 起到了标记的作用。

补充知识：

  1. 曼哈顿距离（ Manhattan Distance）：
    • (x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1|
  2. 宽度优先遍历及其扩展：
    1. 宽度优先遍历与优先级队列结合 - Dijkstra算法。
    2. 可以用宽度优先遍历与深度优先遍历结合，去生成路径：
      1. bfs建图
      2. dfs利用图生成路径

例题分析：

题目1

地图分析
测试链接 : https://leetcode.cn/problems/as-far-from-land-as-possible/

1
2
3
4
5
6
你现在手里有一份大小为 n x n 的 网格 grid
上面的每个 单元格 都用 0 和 1 标记好了其中 0 代表海洋，1 代表陆地。
请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的
并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：
(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

经典 BFS 问题，直接套用BFS模板返回深度减一即可。

题目2

贴纸拼词
测试链接 : https://leetcode.cn/problems/stickers-to-spell-word/

1
2
3
4
5
6
我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们
如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1
注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的
并且 target 被选择为两个随机单词的连接。

可以用DP做，也可以用BFS暴搜，关键在于剪枝的设计。
本题剪枝的设计在于 - “每一次选择都尽可能的消除前缀”。
前缀是来自于题目 target 的设计，因为排序不影响结果，所以排序之后，
会出现类似 “aaabbbccff……”的字符串。
对于 stickers 而言，也是一样，在排序之后，也会出现类似“aaabbcc……”的字符串。
所以对于每层搜索，即每轮 选择 stickers 的过程中，都尽可能的去选择可以消除前缀的字符串，所以这就要求我们额外维护一个26个字符大小的 List 去记录那些可以消除对应前缀的词，既可以记录，也可以防止再次访问。

题目3

到达角落需要移除障碍物的最小数目
测试链接 : https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/

1
2
3
4
5
6
7
给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n
每个单元格都是两个值之一：
0 表示一个 空 单元格，
1 表示一个可以移除的 障碍物
你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) 
返回需要移除的障碍物的最小数目

把墙看作 权 为1的边，通路看作 权 为0的边，题目转化为 01BFS模板题。

题目4

使网格图至少有一条有效路径的最小代价
测试链接 : leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid

1
2
3
4
5
6
7
8
9
给你一个 m * n 的网格图 grid 。 grid 中每个格子都有一个数字
对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：
1 : 往右   2：往左   3：往下   4：往上
注意网格图中可能会有无效数字 ，因为它们可能指向grid以外的区域
从最左上角的格子 (0,0) 出发，有效路径为每一步都顺着数字对应方向走
最终在最右下角的格子 (m - 1, n - 1) 结束的路径
有效路径 不需要是最短路径
可以花费1的代价修改一个格子中的数字，但每个格子中的数字只能修改一次
返回让网格图至少有一条有效路径的最小代价

顺着箭头走可以看作 权 为0的边，花费cost走可以看作 权 为 1的边，转换为标准 01BFS模板。

题目5

二维接雨水
测试链接 : https://leetcode.cn/problems/trapping-rain-water-ii/

1
2
给你一个 m * n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度
请计算图中形状最多能接多少体积的雨水。

前置题目：双指针技巧 - 42. 接雨水
技巧：1. 宽度优先遍历与优先级队列结合

其核心在于考察薄弱点。
维护一个 以水线为比较逻辑 的 小根堆。
先将边缘点加入 小根堆 中然后每次对堆顶操作：
将堆顶节点的 影响节点 加入堆中。
如果 可以影响水线，则加入时传播水线影响，如果 不能影响 则保持原高度。
时间复杂度：O(n * m * lbm)
#### 题目6
单词接龙 II
测试链接 : https://leetcode.cn/problems/word-ladder-ii/
1
2
3
4
5
6
7
8
9
10
11
按字典 wordList 完成从单词 beginWord 到单词 endWord 转化
一个表示此过程的 转换序列 是形式上像 
beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
每对相邻的单词之间仅有单个字母不同
转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词
注意，beginWord 不必是字典 wordList 中的单词
sk == endWord
给你两个单词 beginWord 和 endWord ，以及一个字典 wordList
请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列
如果不存在这样的转换序列，返回一个空列表
每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回

要点：
1. bfs反向建图：正向遍历，逆向索引。
2. dfs利用构建的 反向图 生成路径。
3. 反向比对 <- 不是通过遍历表内字符比对，而是主动改变单词自身然后去表中比对（假设是hash表）

双向BFS

前置知识：

  1. 经典递归过程解析
  2. 根据数据量猜解法
  3. 宽度优先遍历及其扩展

双向BFS（Bidirectional Breadth-First Search）

双向BFS（Bidirectional Breadth-First Search）是一种高效的图搜索算法，它通过从起点和终点同时进行广度优先搜索（BFS），直到两个搜索方向在某个节点相遇，从而找到起点到终点的最短路径。相比传统的单向BFS，双向BFS通常在搜索空间较大时具有更高的效率。
双向BFS相较于单向BFS有显著优势：

  • 搜索空间减小：由于从起点和终点同时逼近，搜索范围大大缩小，通常只需探索图中较小的一部分。
  • 时间复杂度优化：单向BFS的时间复杂度为O(b^d)（b是分支因子，d是路径深度），而双向BFS的最坏时间复杂度为O(b^{d/2})，效率更高。

双向广搜常见用途：

  1. 小优化 - bfs的剪枝策略，分两侧展开分支，哪侧数量少就从哪侧展开
  2. 用于解决特征很明显的一类问题：
    • 特征：全量样本不允许递归完全展开，但是半量样本可以完全展开
    • 过程：把数据分成两部分，每部分 各自展开 计算结果，然后设计两部分结果的 整合逻辑

例题分析：

题目1

单词接龙
测试链接 : https://leetcode.cn/problems/word-ladder

1
2
3
4
5
6
7
8
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列
是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk ：
每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中
注意， beginWord 不需要在 wordList 中。sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList
返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目
如果不存在这样的转换序列，返回 0 。

参考 [[2025-04-01]] <- 126. 单词接龙 II
本题使用 双向BFS ，从 beginWord 和 endWord 相向进行BFS。
维护三个 HashSet 用于存储较小的一层，较大的一层和较小的一层拓展出的下一层。
每次BFS都让较小的一层往下拓展，直到相遇或者无可拓展为止。

另外，实际上 dict表 也起到了 Visited数组 的作用。
时间复杂度：O(26 * wordLength * wordListSize)

题目2

零食问题 & 世界冰球锦标赛
测试链接 : https://www.nowcoder.com/practice/d94bb2fa461d42bcb4c0f2b94f5d4281
测试链接 : https://www.luogu.com.cn/problem/P4799

1
2
3
4
5
6
牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w
牛牛家里一共有n袋零食, 第i袋零食体积为v[i]
牛牛想知道在总体积不超过背包容量的情况下
一共有多少种零食放法(总体积为0也算一种放法)
数据量描述:
1 <= n <= 40, 1 <= w <= 2 * 10^9, 0 <= v[i] <= 10^9

看似背包问题让人秒想到DP，实际上数据量太大，DP建表直接给你内存干爆。
所以只能暴力搜索，但是2^40的的超大规模不可能搜的完啊，
这时候就要用到技巧：我们可以将输入分为左右两个区间，
分别对每一个部分进行暴力搜索，然后开两个数组分别收集左右区间返回值，
然后排序，不回退双指针收集答案。

时间复杂度：O(2^(N/2) + 2^(N/2) + 2^(N/2))

题目3

最接近目标值的子序列和
测试链接 : https://leetcode.cn/problems/closest-subsequence-sum

1
2
3
4
5
6
7
8
9
给你一个整数数组 nums 和一个目标值 goal
你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal
也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal)
返回 abs(sum - goal) 可能的 最小值
注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。
数据量描述:
1 <= nums.length <= 40
-10^7 <= nums[i] <= 10^7
-10^9 <= goal <= 10^9

同上

Dijkstra算法、分层图最短路

前置知识：

  1. 堆结构
  2. 位图，用一个整型变量最多可以表示32个状态，并且非常方便、快速
  3. 建图、链式前向星
  4. 最小生成树 - prim算法利用反向索引堆做的优化
  5. 宽度优先遍历及其扩展

Dijkstra算法及其优化

Dijkstra算法：给定一个源点，求解从源点到每个点的最短路径长度，即求单源最短路径算法。
适用范围：有向图、边的权值没有负数
代码实现：

  1. 彻底暴力的实现：时间复杂度太差、无意义

  2. 普通堆实现的Dijkstra算法：最普遍、最常用

    • 算法核心过程：
      1. 节点弹出过就忽略
      2. 节点没弹出过，让其它没弹出节点距离变小的记录加入堆

  3. 反向索引堆实现的Dijkstra算法：最快速、最极致 - 核心在于掌握反向索引堆

  4. 斐波那契堆优化Dijkstra算法：理论最优，但是常数时间大，代码难度大。

    斐波那契堆

暴力实现的Dijkstra算法 - 朴素 Dijkstra

时间复杂度：O(N²)

  1. 初始化：
    1. 将源节点的距离设为0，其他节点的距离设为无穷大（通常用INF表示）。
    2. 创建一个集合（通常用布尔数组表示）来标记已处理（即已找到最短路径）的节点，初始时为空。
  2. 迭代：
    1. 在未处理的节点中，找到距离源节点当前最小的节点。
    2. 将该节点标记为已处理。
    3. 更新该节点的所有邻接节点的距离：如果通过该节点到达邻接节点的路径比已知路径更短，则更新距离。
  3. 终止：
    1. 重复上述步骤，直到所有节点都被处理，或者剩余节点不可达。

普通堆实现的Dijkstra算法

时间复杂度：O((N+M) log N)

  1. distance[i]表示从源点到i点的最短距离，visited[i]表示i节点是否从小根堆弹出过
  2. 准备好小根堆，小根堆存放记录：(x点，源点到x的距离)，小根堆根据距离组织
  3. 令distance[源点]=0，(源点，0)进入小根堆
  4. 从小根堆弹出(u点，源点到u的距离)
    1. 如果visited[u] == true，不做任何处理，重复步骤4
    2. 如果visited[u] == false，令visited[u] = true，u就算弹出过了
    • 然后考察u的每一条边，假设某边去往v，边权为w
      1. 如果visited[v] == false 并且 distance[u] + w < distance[v]
        令distance[v] = distance[u] + w，把(v, distance[u] + w)加入小根堆
      2. 处理完u的每一条边之后，重复步骤4
  5. 小根堆为空过程结束，distance表记录了源点到每个节点的最短距离。

反向索引堆实现的Dijkstra算法

时间复杂度：O(M log N)

  1. 准备好反向索引堆，根据源点到当前点的距离组织小根堆，可以做到如下操作
    1. 新增记录(x, 源点到x的距离)
    2. 当源点到x的距离更新时，可以进行堆的调整
    3. x点一旦弹出，以后忽略x
    4. 弹出堆顶的记录(u, 源点到u的距离)
  2. 把(源点，0)加入反向索引堆，过程开始
  3. 反向索引堆弹出(u，源点到u的距离)，考察u的每一条边，假设某边去往v，边权为w
    1. 如果v没有进入过反向索引堆里，新增记录(v, 源点到u的距离 + w)
    2. 如果v曾经从反向索引堆弹出过，忽略
    3. 如果v在反向索引堆里，看看源点到v的距离能不能变得更小，如果能，调整堆；不能，忽略
    4. 处理完u的每一条边，重复步骤3
  4. 引堆为空过程结束。反向索引堆里记录了源点到每个节点的最短距离。

分层图最短路

分层图最短路，又叫扩点最短路。
不把实际位置看做图上的点，而是把 实际位置及其状态的组合 看做是图上的点，然后搜索
bfs 或者 Dijkstra的过程不变，只是扩了点（分层）而已
原理简单，核心在于如何扩点、如何到达、如何算距离，每个题可能都不一样

例题分析：

题目1

Dijkstra算法模版
普通堆的实现
测试链接: https://leetcode.cn/problems/network-delay-time
反向索引堆的实现
测试链接: https://www.luogu.com.cn/problem/P4779

题目2

最小体力消耗路径
测试链接: https://leetcode.cn/problems/path-with-minimum-effort/

1
2
3
4
5
6
7
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights
其中 heights[row][col] 表示格子 (row, col) 的高度
一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) 
（注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动
你想要找到耗费 体力 最小的一条路径
一条路径耗费的体力值是路径上相邻格子之间，高度差绝对值的最大值
请你返回从左上角走到右下角的最小 体力消耗值

经典Dijkstra算法模板题

题目3

水位上升的泳池中游泳
测试链接: https://leetcode.cn/problems/swim-in-rising-water/

1
2
3
4
5
6
7
8
在一个 n x n 的整数矩阵 grid 中
每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度
当开始下雨时，在时间为 t 时，水池中的水位为 t
你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台
假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的
当然，在你游泳的时候你必须待在坐标方格里面。
你从坐标方格的左上平台 (0，0) 出发
返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间

经典Dijkstra算法模板，就是要搞清楚什么是代价，在这里，代价就是你要额外等的时间。

题目4

获取所有钥匙的最短路径
测试链接: https://leetcode.cn/problems/shortest-path-to-get-all-keys

1
2
3
4
5
6
7
8
9
10
11
给定一个二维网格 grid ，其中：
'.' 代表一个空房间、'#' 代表一堵墙、’@' 是起点
小写字母代表钥匙、大写字母代表锁
从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间
不能在网格外面行走，也无法穿过一堵墙
如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，
字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母
换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁
另外，代表钥匙和锁的字母互为大小写并按字母顺序排列
返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

经典分层图最短路 + BFS，就是在考虑路径的同时考虑当前路径的状态，以此扩点分层。

题目5

电动车游城市
测试链接: https://leetcode.cn/problems/DFPeFJ/

1
2
3
4
5
6
7
8
小明的电动车电量充满时可行驶距离为 cnt
每行驶 1 单位距离消耗 1 单位电量，且花费 1 单位时间
小明想选择电动车作为代步工具。地图上共有 N 个景点，景点编号为 0 ~ N-1
他将地图信息以 [城市 A 编号,城市 B 编号,两城市间距离] 格式整理在在二维数组 paths，
表示城市 A、B 间存在双向通路。
初始状态，电动车电量为 0。每个城市都设有充电桩，
charge[i] 表示第 i 个城市每充 1 单位电量需要花费的单位时间。
请返回小明最少需要花费多少单位时间从起点城市 start 抵达终点城市 end

经典分层最短路 + Dijkstra算法，
本题扩点的思路：按照 城市 以及到达 城市 时的 电量 以及 花费时间 扩点。

题目6

飞行路线
测试链接 : https://www.luogu.com.cn/problem/P4568

1
2
3
4
5
6
Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司
该航空公司一共在n个城市设有业务，设这些城市分别标记为0 ~ n−1
一共有m种航线，每种航线连接两个城市，并且航线有一定的价格
Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机
航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机
那么 Alice 和 Bob 这次出行最少花费多少

经典分层最短路 + Dijkstra算法，
本题扩点的思路：按照 免单次数 设置状态以扩点。

A*、Floyd、Bellman-Floyd、SPFA

前置知识:

  1. 建图、链式前向星
  2. 宽度优先遍历
  3. Dijkstra算法

A* 算法

A* 算法：指定源点，指定目标点，求源点到达目标点的最短距离
和Dijkstra算法类似，是单源最短路算法
增加了当前点到终点的预估函数
在堆中根据 从源点出发到达当前点的距离+当前点到终点的预估距离 来进行排序
剩下的所有细节和Dijskra算法完全一致

预估函数要求：==当前点到终点的预估距离 <= 当前点到终点的真实最短距离

预估函数是一种吸引力：

  1. 合适的吸引力可以提升算法的速度，吸引力过强会出现错误
  2. 保证 预估距离 <= 真实最短距离 的情况下，尽量接近真实最短距离，可以做到功能正确 且 最快

预估终点距离经常选择：

  1. 曼哈顿距离
  2. 欧式距离
  3. 对角线距离（切比雪夫距离）

Floyd算法

Floyd算法，得到图中任意两点之间的最短距离
时间复杂度O(n^3)，空间复杂度O(n^2)，常数时间小，容易实现
适用于任何图，不管有向无向、不管边权正负、但是不能有负环（保证最短路存在）

过程简述:

  1. distance[i][j]表示i和j之间的最短距离
  2. distance[i][j] = min ( distance[i][j] , distance[i][k] + distance[k][j])
  3. 枚举所有的k即可，实现时一定要最先枚举跳板！

Bellman-Ford算法

Bellman-Ford算法，
解决可以有负权边但是不能有负环（保证最短路存在）的图的单源最短路算法

  • 松弛操作：
    假设源点为A，从A到任意点F的最短距离为distance[F]
    假设从点P出发某条边，去往点S，边权为W
    如果发现，distance[P] + W < distance[S]，也就是通过该边可以让distance[S]变小
    那么就说，P出发的这条边对点S进行了松弛操作

Bellman-Ford过程

  1. 每一轮考察每条边，每条边都尝试进行 松弛操作，那么若干点的distance会变小
  2. 当某一轮发现不再有 松弛操作 出现时，算法停止

Bellman-Ford算法时间复杂度：
假设点的数量为N，边的数量为M，每一轮时间复杂度O(M)
最短路存在的情况下，因为1次松弛操作会使1个点的最短路的边数+1
而从源点出发到任何点的最短路最多走过全部的n个点，所以松弛的轮数必然 <= n - 1
所以Bellman-Ford算法时间复杂度O(M*N)

重要推广：判断从某个点出发能不能到达负环
上面已经说了，如果从A出发存在最短路（没有负环），
那么松弛的轮数必然 <= n - 1
而如果从A点出发到达一个负环，那么松弛操作显然会无休止地进行下去
所以，如果发现从A点出发，在第n轮时松弛操作依然存在，说明从A点出发能够到达一个负环

Bellman-Ford + SPFA优化（Shortest Path Faster Algorithm）

很轻易就能发现，每一轮考察所有的边看看能否做松弛操作是不必要的
因为只有上一次被某条边松弛过的节点，所连接的边，才有可能引起下一次的松弛操作
所以用队列来维护 “这一轮哪些节点的distance变小了”
下一轮只需要对这些点的所有边，考察有没有松弛操作即可

  • SPFA只优化了常数时间，在大多数情况下跑得很快，但时间复杂度为O(n*m)

    看复杂度就知道只适用于小图，根据数据量谨慎使用，在没有负权边时要使用Dijkstra算法

Bellman-Ford + SPFA优化的用途：

  1. 适用于小图
  2. 解决有负边（没有负环）的图的单源最短路径问题
  3. 可以判断从某个点出发是否能遇到负环，如果想判断整张有向图有没有负环，需要设置虚拟源点
  4. 并行计算时会有很大优势，因为每一轮多点判断松弛操作是相互独立的，可以交给多线程处理

注意：
SPFA的另一个重要的用途是解决“费用流”问题，当然也可以被 Primal-Dual原始对偶算法 替代

例题分析：

题目1

Floyd算法模版（洛谷）
测试链接 : https://www.luogu.com.cn/problem/P2910

题目2

Bellman-Ford算法应用（Leetcode）
测试链接 : https://leetcode.cn/problems/cheapest-flights-within-k-stops/

Bellman-Ford算法模板题，但是要注意的是，有可能一轮会更新两次甚至多次距离，导致不足期望次数就更新完毕了。所以要做一个设计：
分开两个表存数据 cur 和 next ，每轮拿数据从cur 拿，保存到 next 中。

题目3

Bellman-Ford + SPFA优化（洛谷）
测试链接 : https://www.luogu.com.cn/problem/P3385

1
2
3
给定一个 n个点的有向图
请求出图中是否存在从顶点 1 出发能到达的负环
负环的定义是：一条边权之和为负数的回路。