Algorithm Index

算法篇

目录
一、搜索算法
1、 深度优先搜索（DFS）
2、 广度优先搜索（BFS）
3、 记忆化搜索——一种类似DP的搜索方法
4、 A*A*启发式搜索及其相应变种
5、 博弈问题
6、 搜索的优化——剪枝
二、基础算法
1、 枚举
2、 几种常见常用的排序算法
3、 贪心（Greedy）
4、 贪心的贪心——动态规划（DP）
（1） 线性规划
（2） 树型动态规划
（3） 状态压缩的动态规划
（4） 动态规划的优化
5、 分而治之——分治法
6、 随机化及其应用
三、图论算法
1、 最小生成树的两种算法（Prim、Kruscal）
2、 求最短路径的算法（Dijkstra、Floyed、Bellman-Ford、SPFA）
3、 求图的强连通分量——洪水灌溉法（FloodFill）
4、 图中环的相关问题
（1） 拓扑排序（TopoSort）
（2） 块及块的收缩
5、 图的割点与桥
6、 凸包（扫描线、Graham-Scan）
7、 利用Bellman-Ford的差分约束系统
四、网络流
1、 Ford-FulkersonFord-Fulkerson及Edmonds-Karp
2、 基于分层思想的算法——Dinic
3、 预流推进及相关算法
4、 特殊的图——二分图
（3） 二分图的最大匹配——超级源点、汇点法及匈牙利法
（4） 二分图的最优匹配——最小费用最大流
（5） 二分图的独立集和支配集
5、最小切割最大流定理
6、最大流的增广路算法——KM算法
五、其他
1、 区间最大最小值问题——RMQ
2、 树的最近公共祖先问题——LCA