大话搜索从状态空间建模到 DFS、BFS 与双向搜索 —— leetcode 题解仓库搜索专题精讲【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode搜索是算法面试与竞赛中最常见的题型之一在有限状态空间中进行枚举穷尽所有可能以找到符合条件的解或解的个数。本文基于 leetcode 题解仓库的《大话搜索》专题thinkings/search.md亦收录于仓库总目录 SUMMARY.md 的第一章 - 算法专题之下系统讲解搜索问题的核心本质——状态空间即图并深入剖析 DFS、BFS 两大基础遍历算法及其衍生技巧前序/后序遍历、迭代加深、双向搜索、双端队列 0-1 BFS。读完本文你将掌握一套从题目描述到状态空间建模再到选择遍历策略与剪枝优化的完整解题方法论。为什么搜索如此重要搜索算法覆盖面极广DFS、BFS、A* 等都属于搜索的范畴。在 leetcode 题解仓库中作者在公开演讲中反复强调前端算法面试中搜索类题目占据了很大比重尤其是国内公司。而搜索专题内部还有大量子专题——状态记录与维护、剪枝、连通分量、拓扑排序等BFS、DFS 只是其中最基础的部分。即便只看 DFS 与 BFS 两种基本算法可玩的花样也非常多BFS 的双向搜索、DFS 的前中后序选择、迭代加深等等。仓库中与之呼应的专题还包括 深度优先遍历、回溯、二叉树的遍历 与 小岛问题。一个重要的事实是搜索并不局限于数组、链表、树等特定数据结构。题目给的是数组状态空间却可能是树或图题目给的是二维网格状态空间却是一张隐式图。数据结构只是载体状态空间才是搜索的真正舞台。搜索的核心是什么搜索题目的本质可以浓缩为一句话将题目中的状态映射为图中的点将状态间的联系映射为图中的边根据题目信息构建状态空间然后对状态空间进行遍历遍历过程需要记录和维护状态并通过剪枝和数据结构等提高搜索效率。状态空间的数据结构不同会导致算法不同对数组搜索、对树搜索、对图搜索写法截然不同。但必须再次强调这里说的数组、树、图是状态空间的逻辑结构而不是题目给出的数据结构。例如题目给你一个数组让你求所有子集——题目输入是线性的数组可你实际搜索的却是一棵决策树因为这道题对应的状态空间是非线性的。搜索问题的核心关注指标也很多树的深度、图的 DFS 序、图中两点间的距离等。这些指标是完成高级算法拓扑排序、连通分量、最短路径等必不可少的基石都可以通过经典算法实现。这正是作者强调一定要先学好基础数据结构与算法的原因。由于数组、链表、树都可以看作图的特例本文围绕图来讲解再逐步具象化到树等特殊结构。状态空间把题目翻译成图结论先行状态空间其实就是一个图结构。图中的节点表示状态图中的边表示状态之间的联系这种联系就是题目给出的各种关系。搜索题目的状态空间通常是非线性的。以求一个数组的子集为例其状态空间可以按子集长度划分长度为 1 的子集长度为 2 的子集……长度为 n 的子集n 为数组长度如何确定以上所有子集一种可行的方案是采取类似分治的方式逐步确定先确定某个子集的第一个数是什么再确定第二个数是什么以此类推。而如何确定第一个数、第二个数答案就是——暴力枚举所有可能。这句话是搜索问题的核心其他一切都是辅助。以长度为 3 的数组为例第一个数可以是数组中任意一项枚举 n 种情况第二个数可以是除去已被选中数字外的任意一项枚举 n - 1 种情况依此类推。据此可以画出一棵决策树树节点中的数字表示数组下标。根 ┌──────┼──────┐ 0 1 2 ← 第一步n 种选择 ┌─┼─┐ ┌─┼─┐ ┌─┼─┐ 1 2 0 2 0 1 ← 第二步n-1 种选择 │ │ │ │ │ │ 2 1 2 0 1 0 ← 第三步n-2 种选择一些搜索算法正是基于这个朴素思想本质就是模拟这棵决策树。回溯专题中求数组 [1,2,3] 的子集的图解过程见 thinkings/backtrack.md就是这棵决策树的实际执行在每个节点将当前路径加入结果集最终得到 [1]、[1,2]、[1,2,3]、[2]、[2,3]、[3] 六个子集。仓库中的 78. 子集题解、46. 全排列题解 都是这类在决策树上搜索的典型题目。需要记住的是状态空间就是图构建状态空间就是构建图如何构建完全取决于题目描述。DFS 深度优先搜索DFS 的概念来自图论但搜索中的 DFS 与图论中的 DFS 略有区别搜索中的 DFS 一般指通过递归函数实现暴力枚举不适用递归时也可以用栈实现本质类似。将题目的状态空间映射到一张图状态是节点状态间联系是边后DFS 就是在这张图上做深度优先遍历BFS 则是广度优先、一层层铺开。BFS 和 DFS 只是遍历这张状态图的两种方式如何构建状态图才是关键。本质上对图遍历会生成一棵搜索树。为了避免重复访问需要记录已经访问过的节点——这是所有搜索算法共有的要求。如果直接在树上遍历树是无环的自然不需要记录访问状态。算法流程首先将根节点放入stack中。从 stack 中取出第一个节点并检验它是否为目标。如果找到目标则结束搜寻并回传结果否则将它某一个尚未检验过的直接子节点加入 stack 中。重复步骤 2。如果不存在未检测过的直接子节点将上一级节点加入 stack 中重复步骤 2。重复步骤 4。若 stack 为空表示整张图都已检查完毕——即图中没有欲搜寻的目标结束搜寻并回传找不到目标。这里的 stack 可以理解为自实现的栈也可以理解为递归时的调用栈。算法模板借助递归完成 DFS 的通用模板如下与 thinkings/DFS.md 中的模板一致const visited {} function dfs(i) { if (满足特定条件{ // 返回结果 or 退出搜索空间 } visited[i] true // 将当前状态标为已搜索 for (根据i能到达的下个状态j) { if (!visited[j]) { // 如果状态j没有被搜索过 dfs(j) } } }模板中有三个关键动作判断终止条件、标记访问状态、枚举可达的下一个状态。若要在此基础上实现回溯撤销选择只需在递归返回后执行undo(i)恢复现场即可详见 回溯专题 的模板。而当状态空间是二维网格时visited 甚至可以省去——200. 岛屿数量题解 的做法是将已经访问过的陆地1直接置为0从而用原地修改替代额外空间这是二维网格 DFS 的重要优化。常用技巧前序遍历与后序遍历DFS 常见形式有前序和后序两种二者的使用场景截然不同。搜索过程中当前点的结果往往需要依赖其他节点此时遍历顺序就变得至关重要当前节点依赖子节点的信息→ 使用后序遍历自底向上递推。当前节点依赖父节点的信息→ 使用先序遍历自顶向下递归。计算树的深度递归公式为 $f(x) f(y) 1$其中 $f(x)$ 表示节点 $x$ 的深度$x$ 是 $y$ 的子节点base case 是根节点深度为 1。由于需要父节点的信息向下传递使用先序遍历自顶向下统计最简单直接。计算树的子节点个数递归公式为 $f(x) \sum_{i0}^{n}{f(a_i)}$其中 $a_i$ 为节点 $x$ 的子节点base case 是叶子节点 $f(x) 1$。由于需要子节点的信息向上汇总使用后序遍历自底向上统计。关于如何从递推关系反推遍历顺序作者在《91 天学算法》91/README.md的《模拟枚举与递推》子专题中有更详细的阐述树的各种遍历方法则集中在 树专题 与 二叉树的遍历 中。迭代加深迭代加深本质上是一种可行性剪枝。当递归树比较深时通过设定递归深度阈值、超过阈值就退出的方式主动减少递归深度。它成立的前提是题目明确告知答案不超过 xxx这样把 xxx 设为递归深度阈值既不会错过正确解又能在极端情况下有效减少不必要的运算。实现上用自顶向下方式记录递归树的层次与计算树深度的方式相同在主逻辑前增加当前层次是否超过阈值的判断即可MAX_LEVEL 20 def dfs(root, level): if level MAX_LEVEL: return # 主逻辑 dfs(root, 0)这种技巧在实际使用中并不常见但在某些场景能发挥意想不到的作用。双向搜索DFS 版有时候问题规模很大直接搜索会超时。此时可以考虑从起点搜索到问题规模的一半将中间产生的状态存起来然后把目标转化为在存储的中间状态中寻找满足条件的组合从而降低时间复杂度。以1755. 最接近目标值的子序列和Closest Subsequence Sum为例完整题目描述如下给你一个整数数组 nums 和一个目标值 goal 。 你需要从 nums 中选出一个子序列使子序列元素总和最接近 goal 。也就是说如果子序列元素和为 sum 你需要最小化绝对差 abs(sum - goal) 。 返回 abs(sum - goal) 可能的 最小值 。 注意数组的子序列是通过移除原始数组中的某些元素可能全部或无而形成的数组。 示例 1 输入nums [5,-7,3,5], goal 6 输出0 解释选择整个数组作为选出的子序列元素和为 6 。子序列和与目标值相等所以绝对差为 0 。 示例 2 输入nums [7,-9,15,-2], goal -5 输出1 解释选出子序列 [7,-9,-2] 元素和为 -4 。绝对差为 abs(-4 - (-5)) abs(1) 1 是可能的最小值。 示例 3 输入nums [1,2,3], goal -7 输出7 提示 1 nums.length 40 -10^7 nums[i] 10^7 -10^9 goal 10^9思路分析从数据范围可以看出这道题大概率是一个 $O(2^m)$ 时间复杂度的解法其中 m 是 nums.length 的一半。经验法则数组长度 ≤ 20 时大概率是 $O(2^n)$ 的解法而40 这个数字本身就是强烈信号——把它砍半恰好就能 AC。这是因为可以用一个二进制位表示原数组 nums 的一个子集用一个长度为 $2^n$ 的数组描述所有子集这就是状态压缩题目数据范围 ≤ 20 时都应该想到它。接下来用动态规划求出所有子集和。令dp[i]表示选择情况如 i 所示的和用一个位数足够的数二进制位数需大于 n的二进制表示一种选择情况0 表示选择、1 表示不选择。枚举数组每一项将其加入选择转移方程为dp[(1 i) j] dp[j] A[i]其中 j 为 i 的子集。动态规划求子集和代码如下def combine_sum(A): n len(A) dp [0] * (1 n) for i in range(n): for j in range(1 i): dp[(1 i) j] dp[j] A[i] # 将 i 加入选择 return dp将 nums 平分为两部分分别计算子集和n len(nums) c1 combine_sum(nums[: n // 2]) c2 combine_sum(nums[n // 2 :])其中 c1 是前半部分数组的子集和c2 是后半部分的子集和。问题转化为在两个数组 c1 和 c2 中各找一个数使其和最接近 goal——这是一个非常经典的双指针问题逻辑类似两数之和只不过两数之和是在一个数组中挑两个数这里是两个数组分别挑一个数。只需一个指针指向数组头另一个指向数组尾def combine_closest(c1, c2): # 先排序以便使用双指针 c1.sort() c2.sort() ans float(inf) i, j 0, len(c2) - 1 while i len(c1) and j 0: _sum c1[i] c2[j] ans min(ans, abs(_sum - goal)) if _sum goal: j - 1 elif _sum goal: i 1 else: return 0 return ans完整题解代码如下class Solution: def minAbsDifference(self, nums: List[int], goal: int) - int: def combine_sum(A): n len(A) dp [0] * (1 n) for i in range(n): for j in range(1 i): dp[(1 i) j] dp[j] A[i] return dp def combine_closest(c1, c2): c1.sort() c2.sort() ans float(inf) i, j 0, len(c2) - 1 while i len(c1) and j 0: _sum c1[i] c2[j] ans min(ans, abs(_sum - goal)) if _sum goal: j - 1 elif _sum goal: i 1 else: return 0 return ans n len(nums) return combine_closest(combine_sum(nums[: n // 2]), combine_sum(nums[n // 2 :]))复杂度分析令 n 为数组长度m 为 $\frac{n}{2}$时间复杂度$O(m*2^m)$空间复杂度$O(2^m)$同类题型还可练习16. 最接近的三数之和、1049. 最后一块石头的重量 II、1774. 最接近目标价格的甜点成本。这道题和双向搜索有什么关系回顾开头的话问题规模很大时直接搜索会超时此时可以考虑搜索到一半将状态存起来再把目标转化为在中间状态中寻找满足条件的状态。对应这道题直接暴力枚举所有子集和再找最接近 goal 的会超时于是搜索到一半、把状态存到 dp 数组问题转化为两个 dp 数组的运算。该算法本质上是把位于指数位的常数项挪动到了系数位——这是一种常见的双向搜索可称为DFS 的双向搜索以区别于后面的 BFS 双向搜索。BFS 广度优先搜索BFS 也源自图论与 DFS 不同它采用横向搜索方式从初始状态一层层展开直到目标状态数据结构上通常采用队列。具体过程不断从队头取出状态将此状态对应的决策产生的所有新状态推入队尾重复直到队列为空。这里有两个关键点将此状态对应的决策指的正是状态空间中图的边。DFS 和 BFS 的决策边是确定的、完全相同的不同的是进行决策的方向。所有新的状态推入队尾由于将当前点的所有邻边全部放到队尾利用队列先进先出的特性在当前点的所有邻边访问完成之前不会继续向外扩展——这正是 BFS 与 DFS 在方向上的差异体现。最简单的 BFS 每次扩展新状态就增加一步等价于在一个权值为 1 的图上进行 BFS。由于队列的单调性和二值性第一次取出目标状态时就是最少步数。基于此特性BFS 适合求解最少操作类题目。前面提到所有搜索都需要记录和维护状态防止环的产生。BFS 中常用一个哈希表 dist 记录从源点到图中其他点的距离——dist 同时充当防止环产生的功能第一次到达某点后再次到达该点的距离一定比第一次大据此即可判断是否为首次访问。算法流程首先将根节点放入队列中。从队列中取出第一个节点并检验它是否为目标。如果找到目标则结束搜索并回传结果。否则将它所有尚未检验过的直接子节点加入队列中。若队列为空表示整张图都检查过了——亦即图中没有欲搜索的目标结束搜索并回传找不到目标。重复步骤 2。算法模板const visited {} function bfs() { let q new Queue() q.push(初始状态) while(q.length) { let i q.pop() if (visited[i]) continue for (i的可抵达状态j) { if (j 合法) { q.push(j) } } } // 找到所有合法解 }仓库中 102. 二叉树的层序遍历题解 就是 BFS 模板在树上最直接的应用——每层节点天然构成队列中的一层层序遍历即树的 BFS。常用技巧双向搜索BFS 版以126. 单词接龙 IIWord Ladder II为例完整题目描述如下按字典 wordList 完成从单词 beginWord 到单词 endWord 转化一个表示此过程的转换序列是形式上像 beginWord - s1 - s2 - ... - sk 这样的单词序列并满足 每对相邻的单词之间仅有单个字母不同。 转换过程中的每个单词 si1 i k必须是字典 wordList 中的单词。注意beginWord 不必是字典 wordList 中的单词。 sk endWord 给你两个单词 beginWord 和 endWord 以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的最短转换序列如果不存在这样的转换序列返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。 示例 1 输入beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log,cog] 输出[[hit,hot,dot,dog,cog],[hit,hot,lot,log,cog]] 解释存在 2 种最短的转换序列 hit - hot - dot - dog - cog hit - hot - lot - log - cog 示例 2 输入beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log] 输出[] 解释endWord cog 不在字典 wordList 中所以不存在符合要求的转换序列。 提示 1 beginWord.length 7 endWord.length beginWord.length 1 wordList.length 5000 wordList[i].length beginWord.length beginWord、endWord 和 wordList[i] 由小写英文字母组成 beginWord ! endWord wordList 中的所有单词 互不相同思路分析这就是日常玩的成语接龙游戏只不过接龙规则是下一个单词与上一个单词仅有单个字母不同。对问题进行抽象构建一个大小为 n 的图图中每个点表示一个单词目标是找到从 beginWord 到 endWord 的最短路径——这是一个不折不扣的图上 BFS 题目套用上面的模板即可。唯一需要注意的是如何构建图更进一步说是如何构建边。由转换规则每对相邻单词仅有一个字母不同可知两个单词仅有一个字母不同就说明两者之间有一条边。据此可以构建邻接表核心代码neighbors collections.defaultdict(list) for word in wordList: for i in range(len(word)): neighbors[word[:i] * word[i 1 :]].append(word)这里把每个单词的每一位分别替换为通配符*如hit生成*it、h*t、hi*凡是落入同一个通配键的单词之间都只差一个字母天然成边。这是典型的空间换时间预处理。建好图后BFS 只剩明确起点beginWord与终点endWord。将 beginWord 入队在图上做 BFS 直到第一次遇到 endWord。下面这份代码用 cost而非 visited记录到达每个单词的最小转换步数借此展示多种写法class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) - List[List[str]]: cost collections.defaultdict(lambda: float(inf)) cost[beginWord] 0 neighbors collections.defaultdict(list) ans [] for word in wordList: for i in range(len(word)): neighbors[word[:i] * word[i 1 :]].append(word) q collections.deque([[beginWord]]) while q: path q.popleft() cur path[-1] if cur endWord: ans.append(path.copy()) else: for i in range(len(cur)): for neighbor in neighbors[cur[:i] * cur[i 1 :]]: if cost[cur] 1 cost[neighbor]: q.append(path [neighbor]) cost[neighbor] cost[cur] 1 return ans为什么使用双向 BFS当终点可以逆向搜索时可以尝试双向 BFS。更本质地说如果你构建的状态空间的边是双向的那么就可以使用双向 BFS。与 DFS 的双向搜索思想类似只需用两个队列分别存储从起点和终点扩展的节点起点集与终点集当起点集与终点集在某一时刻交汇就说明找到了一条从起点到终点的路径其长度等于两个队列扩展路径长度之和。起点 A 的扩展: A ──► B ──► C ──► D │ 交汇点 X 终点 Z 的扩展: Z ──► Y ──► X ◄───┘从起点和终点分别搜索若两边的扩展状态重叠本质上就是队列中的元素重叠即可拼出最短路径。为什么双向搜索更快什么情况下更快为什么不全用双向搜索有哪些使用条件为什么更快刚开始搜索时边较少、队列中数据也少随着搜索推进搜索树越来越大队列中的节点随之增多这种增长速度很多情况下是指数级的。而双向搜索可以将指数的常系数移动到多项式的系数位。若使用单向搜索搜索树的规模会大得多往往需要画省略号才能装下。什么情况下更快相比单向搜索双向搜索通常更快但也有例外。举个极端例子从起点到终点只有一条路径时无论单向还是双向结果都一样。为什么不全用双向搜索做题时建议尽量使用单向搜索——写起来更简单且大多数情况下能通过所有测试用例除非预估到可能超时或提交后发现超时再尝试双向搜索。有哪些使用条件正如前面所述终点可以逆向搜索、状态空间的边是双向的才能使用双向 BFS。回到单词接龙这道题。为了判断两边是否交汇可以用两个 hashSet 分别存储起点集与终点集当一个节点既出现在起点集又出现在终点集就说明出现了交汇。这里还有一个值得注意的细节——为了节省代码量与空间代码直接使用哈希表代替队列。这种做法可行的关键仍然是队列的二值性和单调性由于新一轮出队列前队列中的权值都是相同的因此从左到右、从右到左甚至任意顺序遍历都无所谓所以用哈希表替代队列完全可行。但这并不意味着永远可以用哈希表代替队列——当边权出现 0 时就不行了下文双端队列部分会揭晓原因。这道题的具体算法定义两个队列 q1 和 q2分别从起点和终点进行搜索。构建邻接表通配符预处理。每次都尝试从 q1 和 q2 中较小的一方进行扩展——这可以起到剪枝效果。如果 q1 和 q2 交汇了则将两者的路径拼接起来。class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: list) - list: # 剪枝 1 if endWord not in wordList: return [] ans [] visited set() q1, q2 {beginWord: [[beginWord]]}, {endWord: [[endWord]]} steps 0 # 预处理空间换时间 neighbors collections.defaultdict(list) for word in wordList: for i in range(len(word)): neighbors[word[:i] * word[i 1 :]].append(word) while q1: # 剪枝 2从较少的端扩展 if len(q1) len(q2): q1, q2 q2, q1 nxt collections.defaultdict(list) for _ in range(len(q1)): word, paths q1.popitem() visited.add(word) for i in range(len(word)): for neighbor in neighbors[word[:i] * word[i 1 :]]: if neighbor in q2: # 从 beginWord 扩展过来的 if paths[0][0] beginWord: ans [path1 path2[::-1] for path1 in paths for path2 in q2[neighbor]] # 从 endWord 扩展过来的 else: ans [path2 path1[::-1] for path1 in paths for path2 in q2[neighbor]] if neighbor in wordList and neighbor not in visited: nxt[neighbor] [path [neighbor] for path in paths] steps 1 # 剪枝 3 if ans and steps 2 len(ans[0]): break q1 nxt return ans总结本题传递的核心知识点队列不一定非得是常规的队列也可以是哈希表等不过某些情况必须是双端队列见下节。双向 BFS 只适合双向图——从终点也能往前推。双向 BFS 从状态较少的一端扩展可以起到剪枝效果。visited 和 dist/cost 都能记录访问情况、防止环的产生不过 dist 的信息量更大相应空间占用也更大。双端队列BFS 本质可看作在边权为 1 的图上遍历。做一个简单扩展如果图中边权不全是 1而是 0 和 1 呢此时就需要用到双端队列deque。双端队列可以在头部和尾部同时进行插入和删除普通队列只允许头部删除、尾部插入。使用双端队列时每次取出一个状态如果我们可以无代价地转移边权为 0就将其直接放在队头如果状态转移是有代价的边权为 1就将其放到队尾。由前面讲的队列单调性和二值性不难得出算法正确性——这也是很多语言内置双端队列而非普通队列的原因之一。普通队列: 队尾 ── [E D C B A] ── 队头 双端队列: 队尾 ── [E D C A] ── 队头B 因无代价转移被插入队头思考题如果图对应的权值不是 0 和 1而是任意正整数呢此时 BFS 不再适用需要考虑 Dijkstra 等算法。回看上一节的悬念是不是不需要队列用哈希表、哈希集合存储就行了答案是不可以——哈希表无法处理权值为 0 的情况这正是必须使用双端队列的场景。DFS 和 BFS 的对比两者都服务于同一个目标对题目对应的状态空间进行搜索。区别在于DFS 在分叉点会任选一条深入遇到终点则返回再次返回到分叉口后尝试下一个选择。基于此可以在路径上记录数据由此衍生出很多有趣的技巧。例如遍历到节点 A 时有三个选择程序任意选择一条比如 B深入再继续往下选择分支 2、3……回溯专题中的经典示意图assets/problems/backtrack.png清晰地展示了这种递归深入 回溯返回的流程绿色箭头表示 DFS 向下递归黄色箭头表示回溯时的向上返回紫色部分则是回溯过程中收集到的有效解集合。BFS 在分叉点会把所有搜索路径各尝试一次。使用队列存储待处理元素时队列中最多只会有两层元素且满足单调性——相同层的元素在一起基于这个特点可以衍生出很多有趣的优化。广度优先遍历会将当前层的所有选择全部遍历完才会进入下一层右侧队列始终最多有两层的节点并且相同层的总在一起即队列元素在层上满足单调性。在二维网格这类典型的图上搜索场景中两者的分工也很明确求连通块个数、可达区域等存在性/计数问题多用 DFS参考 200. 岛屿数量题解 与 小岛问题专题求最短路径、最少步数等最优性问题多用 BFS参考 102. 二叉树的层序遍历题解。总结以上就是 leetcode 题解仓库《搜索篇上》的核心内容。搜索题目的解题思路可以归纳为三步根据题目信息构建状态空间图。对图进行遍历BFS 或 DFS。记录和维护状态visited 维护访问情况队列和栈维护状态的决策方向等。核心要点DFS 通常都是有递推关系的而递归关系就是图的边。根据递推关系依赖父节点还是依赖子节点可以选择前序遍历或后序遍历。BFS 由于其单调性适合求解最短距离问题。双向搜索的本质是将复杂度的常数项从一个影响较大的位置比如指数位移到影响较小的位置比如系数位。visited 与 dist/cost 都可防止环的产生但后者信息更多、空间更大队列可用哈希表替代的前提是二值性 单调性而遇到 0-1 边权时必须使用双端队列。搜索专题知识点密集仓库中与之衔接的下一部分内容还包括回溯与剪枝见 thinkings/backtrack.md以及常用指标与统计方法——树的深度与子树大小见 thinkings/tree.md、图的 DFS 序、图的拓扑序、图的连通分量见 并查集专题。建议将本文与 深度优先遍历、回溯、二叉树的遍历 等专题放在一起交叉学习从状态空间 图这一核心认识出发反复练习建模与遍历方能真正掌握搜索的精髓。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
