搜索算法

搜索算法

搜索是解决复杂问题的通用框架。共 16 个模板。

← 返回模板库

6.1DFS - 全排列

深度优先搜索生成所有排列

O(n!)

6.2DFS - 组合枚举

从 n 个数中选 k 个的所有方案

O(C(n,k))

6.3DFS - 子集枚举

枚举集合的所有子集

O(2^n)

6.4N皇后问题

经典回溯，放置互不攻击的皇后

O(n!)

6.5BFS - 网格迷宫

层序遍历求网格最短路径

O(n × m)

6.6BFS - 最少步数

状态空间搜索求最少操作次数

O(状态数 × 转移数)

6.7泛洪填充（Flood Fill）

连通区域标记与填充

O(n × m)

6.8剪枝技巧

可行性剪枝、最优性剪枝、对称性剪枝

视问题而定

6.9单调栈

维护栈中元素单调性，解决“下一个更大元素”类问题

O(n)

6.10单调队列

维护队列单调性，高效求滑动窗口最值

O(n)

6.11A* 搜索

启发式搜索，估价函数引导优先扩展

O(E log V)

6.12IDA* 迭代加深

深度限制 + 启发函数，空间高效的搜索

视问题而定

6.13双向 BFS

从起点和终点同时搜索，大幅缩小搜索空间

O(b^(d/2))

6.14记忆化搜索

DFS + 缓存，避免重复子问题

O(状态数 × 转移数)

6.15拓扑排序 - DFS

DFS 实现拓扑排序，判断有向图是否有环

O(V + E)

6.16拓扑排序 - BFS（Kahn）

BFS 实现拓扑排序，入度为零的点依次入队

O(V + E)