算法设计
算法基础
- 排序
- 插入排序
- 冒泡排序
- 堆排序
- 快速排序
- 归并排序：分治法 大师定理
- BFS
- 可以用于找寻最短路径 但是只适用于边长1的图 因此效率不高
- 引申出Dijkstra算法 可以用堆来加速
强连通部件
- DFS
- 在每一个部件内调用EXPLORE算法
- 对每个节点 记录两次访问的时间顺序 称为[pre, post] 那么任意两个节点的区间不可能部分相交 证明可能会考 也很简单 如果有树边 那么就是包含；否则就是不相交
- 拓展到有向图 边可以被分为树边、回边以及横跨边
- 有向图有环等价于存在回边 很好证明
- 按照post排序即可得到拓扑序 因为在DAG中没有回边 那么每一条边uv的post一定是v小于u 因此post的逆序就是拓扑序
- SCC
- 所有节点都互相强连通的最大子图
- 任何的有向图 如果基于SCC进行收缩 那么会变为一张DAG 否则不满足最大性
- 如果我们在汇部件上进行EXPLORE 显然可以探索到整个部件 因此我们寻找SCC的算法可以基于这样的思路：反转所有边 然后进行DFS post最大的节点一定来自于反图的源部件 在这个节点上进行EXPLORE 然后找到下一个post最大的节点 以此类推 拥有线性时间复杂度
- 线性复杂度在大图中并不是高效的 因此还有一些其它算法 比如Tarjan、Kosaraju等
MST
- 割
- 一个节点集 划分为S和V-S
- 一个环与割必定相交偶数条边
- 生成树
- 无环且连通的子图 覆盖了所有顶点
- 最小生成树是边cost最小的生成树
- 贪婪算法
- 找到一个没有红色的环 选择其中未染色的最大边 染为红色
- 找到一个没有蓝色的割集 选择其中未染色的最小边 染为蓝色
- 循环执行染色操作 最终得到最小生成树（蓝色）
- Prim算法
- 不断找到一端在S中的最小边加入生成树 重复V-1次即可得到MST
- 等价于一直进行蓝色染色
- 采用堆来维护点cost 和dijk一样 不断更新新加入的边为cost 并选取cost最小的点 复杂度为ElogV
- Kruskal算法
- 先对所有边排序 然后不断加入不成环的最小边
- 等价于按升序对所有边依次染色 如果成环 染红色 否则染蓝色
- 排序和并查集循环的复杂度都是ElogE
- 降序删除算法
- 对所有边降序排序 如果删除这条边会让T不连通 那么保留边 否则删除
- 等价于依次染色 如果破坏 染蓝色 否则染红色
- 复杂度为ElogVloglogV^3
- Boruvka算法（并行算法）
- 需要所有边权不重复 可以通过扰动来实现
- 并行的对于任意蓝色树的割集选出蓝色边 然后一起染色
- 等价于一直进行蓝色染色
- 复杂度为ElogV
- 可以通过不断压缩蓝色树来加速 压缩的复杂度为E+V
- MBST
- 最小瓶颈生成树是最大边权最小的生成树
- 反证可以证明MST都是MBST（否则我们可以引入MBST里的一条更小的边来构造更小的MST）
DP
- DAG的最短路径
- 先拓扑排序 然后从左到右更新dist即可
- 最长递增子序列
- 定义L_j是以j结尾的最长递增子序列即可
- 等价于DAG的最长路径 其中边代表了小于关系
- 序列对齐（编辑距离）
- 定义dp[i][j]是s1前i个字符与s2前j个字符的最优对齐代价
- 序列对齐要求记录下编辑的路径 只需要反向找到每一步的最小值即可
- 有一个算法可以实现m+n的空间复杂度记录路径
- 最长公共子序列
- 编辑距离的对偶问题
- 最长公共子串
- 定义dp[i][j]为i，j结尾的最长公共子串即可
- 需要遍历出dp[i][j]的最大值
- Bellman-Ford算法
- 可以解决负边权图的单源最短路径问题 还可以检测负环
- dp[i][j]是使用最多i条边到节点j的最短路径长度
- 由于表格是一列一列填的 因此空间复杂度可以优化为V 即维护当前每个节点的最短路径长度即可
- 时间复杂度VE
- 如果需要记录路径 额外用一个变量维护每个值是从哪个节点来的即可（即节点的后继者）
- 进行第n轮计算时 如果存在某个节点的最短路径长度小于其n-1的 那么存在负环 否则没有
- 最短可靠路径
- 使用最多k条边的最短路径
- BF即可解决
- 所有节点间的最短路径
- dp[i][j][k]是使用1-k节点的i到j的最短路径长度 分类考虑是否使用k节点即可
- 时间复杂度是V^3 空间复杂度可以优化到V^2
https://nwdnys1.github.io/2026/06/15/课程笔记/算法设计/