当前位置：首页 > news >正文

ACM 全部算法 Python 实现合集：你离算法自由只差这一份实战代码库

news 2026/6/5 3:02:30

刷了 200 道 LeetCode，一到 ACM 真题还是写不出？问题不在"刷题量"，在你没有一份可运行、可调试、可对照理解的算法全案参考。

本仓库将 CSDN 博客《ACM 全部算法总结》中列出的全部算法，逐一生成了通俗易懂的原理讲解 + 可直接运行的 Python Demo。每个.md文件都是一个完整的算法单元，复制代码块即可运行，无需任何第三方依赖。

一、文章总览

项目	内容
文章标题	ACM 全部算法 Python 实现合集
文章副标题	你离算法自由只差这一份实战代码库
目标读者	ACM 参赛者 / 算法学习者 / 面试准备者
核心卖点	所有算法配有白话原理+纯 Python 实现，开箱即跑
覆盖算法数	100+（数据结构 / 图论 / 搜索 / DP / 数论 / 组合 / 几何 / 计算 / 博弈）
环境要求	Python 3.7+，零额外依赖
使用方式	每个`.md`文件 = 一个算法，含完整注释 + 运行示例

二、正文主体

01 数据结构 — 一切算法的地基

如果你只能学好一个模块，那就是数据结构。栈与队列管顺序，堆与树管优先级，并查集与线段树管区间——90% 的算法题本质都是"选对数据结构 + 套用模板"。

编号	算法	一句话说明	难度	核心场景
1	栈 / 队列 / 双端队列	线性结构三件套	★☆☆	表达式求值、BFS、滑动窗口
2	链表 / 哈希表	动态存储与 O(1) 查找	★☆☆	LRU 缓存、去重、映射
3	堆与优先队列	最值快速提取	★★☆	第 K 大、Dijkstra、任务调度
4	左偏堆	可合并堆	★★★	可持久化优先队列
5	二叉查找树 / Treap / 伸展树	动态有序集合	★★★	排名查询、区间操作
6	并查集	集合合并与查询	★★☆	连通分量、Kruskal
7	AVL 平衡树	严格平衡 BST	★★★	高频插入删除的有序数据
8	线段树 / 二维线段树	区间查询与修改	★★★	RMQ、区间和、矩阵操作
9	树状数组 / 二维树状数组	简洁版线段树	★★☆	前缀和、动态逆序对
10	Trie 字典树	字符串前缀匹配	★★☆	自动补全、词频统计
11	后缀数组	子串问题的利器	★★★★	最长公共子串、模式匹配
12	块状链表	兼具数组与链表的优点	★★★	文本编辑器
13	哈夫曼树	最优前缀编码	★★☆	数据压缩
14	跳跃表	概率平衡的序结构	★★★	Redis Zset 底层实现
15	AC 自动机	多模式串匹配	★★★	敏感词过滤
16	LCA / RMQ	树上两点最近公共祖先	★★★	树上路径问题
17	KMP	单模式串匹配	★★☆	字符串查找

02 图论 — 连接一切的艺术

图论是 ACM 的兵家必争之地。从最短路径到最大流，从拓扑排序到强连通分量——图论模块是区分选手水平的分水岭。

图的遍历与基础

编号	算法	一句话说明	难度	核心场景
18	图的存储（邻接矩阵/邻接表）	图的基础表示	★☆☆	一切图算法的前置
19	BFS / DFS	朴素的搜索框架	★☆☆	连通性、最短路径（无权）
20	拓扑排序	DAG 的线性排列	★★☆	任务调度、依赖解析

连通性

编号	算法	一句话说明	难度	核心场景
21	割边 / 割点	去掉后图变不连通的关键边/点	★★★	网络可靠性
22	Tarjan 强连通分量	有向图的 SCC	★★★	缩点、2-SAT
23	双连通分量	无向图的桥与块	★★★	冗余设计
24	2-SAT	布尔变量的可满足性	★★★★	逻辑约束求解
25	欧拉回路 / 哈密顿回路	一笔画 / 旅行商	★★☆ / ★★★★	路径规划

最小生成树

编号	算法	一句话说明	难度	核心场景
26	Prim（堆优化）	加点法 MST	★★☆	稠密图
27	Kruskal（并查集）	加边法 MST	★★☆	稀疏图
28	Borůvka	分治合并式 MST	★★★	特殊图构造
29	次小生成树	严格/非严格次优	★★★	备用网络设计
30	最小树形图	有向图的最小生成树	★★★★	有向图最优路径

最短路径

编号	算法	一句话说明	难度	核心场景
31	Dijkstra（堆优化）	非负权单源最短路	★★☆	最基础的最短路
32	Bellman-Ford / SPFA	负权检测 + 最短路	★★☆ / ★★★	差分约束、负环
33	Floyd	全源最短路（O(n³)）	★★☆	小图多源查询
34	Johnson	全源最短路（稀疏图）	★★★	大规模全源最短路
35	第 K 短路（A*）	次优路径查找	★★★★	路径推荐

网络流与匹配

编号	算法	一句话说明	难度	核心场景
36	Ford-Fulkerson / Dinic	最大流	★★★	网络流基础
37	最小费用最大流	带权最优流	★★★★	运输调度
38	Stoer-Wagner	全局最小割	★★★★	图分割
39	匈牙利算法	二分图最大匹配	★★★	任务分配
40	KM 算法	带权最大匹配	★★★★	最优分配
41	稳定婚姻（Gale-Shapley）	稳定匹配问题	★★☆	匹配市场的稳定性

03 搜索 — 暴力不止，优化有道

搜索不是"暴力穷举"，而是用策略把指数级的空间压缩到可解范围。

编号	算法	一句话说明	难度	核心场景
42	BFS 状态优化	状态压缩 + 去重 BFS	★★★	八数码、最短路变形
43	双向 BFS	从起点终点同时搜索	★★☆	迷宫、单词变换
44	A* 算法	启发式搜索	★★★	游戏 AI、路径规划
45	IDA*	迭代加深 + 启发式	★★★	15-puzzle
46	记忆化搜索	用缓存消除重复递归	★★☆	以搜索形式写 DP
47	剪枝技巧	提前排除不可能的分支	★★☆	任何搜索的加速器

04 动态规划 — 思路决定上限

DP 的核心不是代码，是状态定义。定义对了，转移自然；定义错了，写十年也是暴力。

编号	算法	一句话说明	难度	核心场景
48-50	背包（0-1 / 完全 / 多重 / 分组）	有限容量下的最优选择	★★☆	资源分配
51	数字三角形	经典路径 DP 入门	★☆☆	DP 第一课
52	LIS（最长上升子序列）	O(n log n) 的二分优化	★★☆	序列问题
53	LCS（最长公共子序列）	二维 DP	★★☆	文本 diff
54	区间 DP（石子合并）	枚举断点的区间最优	★★★	矩阵链乘、回文
55	树形 DP	树上递归转移	★★★	树的最优策略
56	状压 DP	状态压缩 + DP	★★★★	旅行商、集合覆盖
57	数位 DP	按位统计的 DP 技巧	★★★	区间数字计数
58	单调队列优化 DP	滑窗 + DP 的加速	★★★★	有限制的分段最优
59	四边形不等式优化	决策单调性剪枝	★★★★★	区间 DP 的复杂度杀手
60	概率与期望 DP	从概率到期望的递推	★★★★	博弈、随机过程

05 数论 — 算法的数学内核

不懂数论的选手，遇到质数、同余、逆元只能打表——而这些都有现成的通解。

编号	算法	一句话说明	难度	核心场景
61	欧几里得 GCD	最大公约数	★☆☆	约分、互质判断
62	扩展欧几里得	求 ax+by=gcd 的整数解	★★★	逆元、同余方程
63	中国剩余定理 CRT	解同余方程组	★★★	大整数表示
64	欧拉函数	小于 n 且与 n 互质的数的个数	★★☆	降幂、密码学
65	素数筛（埃氏 / 欧拉）	快速生成素数表	★★☆	质因数分解前置
66	Miller-Rabin	大数素性检测	★★★	大数判素
67	Pollard-Rho	大数质因数分解	★★★★	大数分解
68	快速幂	O(log n) 计算幂	★☆☆	模幂运算
69	乘法逆元	模意义下的除法	★★☆	组合数取模
70	BSGS	离散对数	★★★	密码学
71	莫比乌斯反演	容斥的数论版本	★★★★★	约数/倍数求和

06 组合数学 — 数清楚"有多少种"

排列组合不是高中数学，是 ACM 中设计状态空间的基础。

编号	算法	一句话说明	难度	核心场景
72	排列组合 & Lucas 定理	大组合数取模	★★★	nCk mod p
73	容斥原理	多集计数的不重不漏	★★★	互质计数
74	卡特兰数	进出栈、二叉树个数	★★☆	合法括号序列
75	斯特林数	集合划分	★★★★	放球问题
76	斐波那契（矩阵快速幂）	递推加速	★★☆	递推类问题
77	错排（德·蒙特莫特）	全都不在原位的排列	★★☆	信件装错
78	Burnside 引理 & Polya 计数	等价类的计数	★★★★★	环上染色
79	N 皇后构造解	N 皇后问题的公式解	★★★	棋盘放置
80	生成函数	用多项式解组合问题	★★★★★	整数拆分

07 计算几何 — 从二维到三维的精度博弈

计算几何的痛点从来不是思路，而是精度、边界和浮点误差。

编号	算法	一句话说明	难度	核心场景
81	向量基础（叉乘 / 点乘）	几何运算的基石	★★☆	方向判断、投影
82	多边形面积	叉积求有向面积	★★☆	任意多边形面积
83	线段相交（跨立实验）	判断两线段是否相交	★★★	碰撞检测
84	点在多边形内（射线法）	点在任意多边形内判断	★★★	地理围栏
85	Andrew 凸包	凸多边形求法	★★★	最小包围图形
86	旋转卡壳	凸包上的最远点对	★★★★	直径、宽度
87	半平面交	直线集合的交集	★★★★	可行域求解
88	最小圆覆盖	随机增量法	★★★★	最小包围圆
89	三角形四心（垂/重/内/外）	三角形经典几何中心	★★☆	计算几何基础
90	圆相关（相交/面积/切线）	圆的各类计算	★★★	圆几何问题
91	三维凸包	三维空间的最小凸多面体	★★★★★	3D 计算几何

08 计算方法 — 计算机做数学的"野路子"

很多问题没有解析解，但数值方法能给你足够好的近似解。

编号	算法	一句话说明	难度	核心场景
92	二分法	单调函数上的精确查找	★☆☆	分治基础
93	三分法	单峰/单谷极值查找	★★☆	函数极值
94	高斯消元	解线性方程组	★★★	电路分析、矩阵求逆
95	矩阵快速幂	线性递推加速	★★★	斐波那契、DP 加速
96	FFT（快速傅里叶变换）	多项式乘法 O(n log n)	★★★★	大整数乘法、卷积
97	辛普森自适应积分	数值积分	★★★	函数面积计算
98	模拟退火	启发式全局寻优	★★★	旅行商、布局优化
99	0/1 分数规划	比值最大化/最小化	★★★★	最优比率生成树

09 博弈论 — 赢在对手之前思考

博弈不是运气，是确定性游戏。"先手必胜"不是玄学，是 SG 函数算出来的。

编号	算法	一句话说明	难度	核心场景
100	极大极小搜索（α-β 剪枝）	博弈树搜索	★★★	棋类 AI
101	Nim 博弈 & SG 函数	公平组合游戏的通用解法	★★★	一切取石子游戏变种

三、使用方式

步骤	操作	说明
1	打开任意`.md`文件	每个文件对应一个算法
2	阅读一句话简介	30 秒判断是否是你需要的算法
3	理解通俗原理	用大白话讲清楚，不堆公式
4	查看代码实现	纯 Python，每行有中文注释
5	复制代码块到`.py`文件	环境: Python 3.7+，零依赖
6	运行验证	每个文件都附带可运行的输入输出示例

想批量验证所有算法？根目录的run_all.py会自动提取所有.md中的 Python 代码块并依次执行：

python run_all.py

如果看到一片绿色的PASS，说明所有 Demo 均已验证通过。

四、学习路径建议

你的水平	建议路径	预计时间
算法新手	数据结构(01) → 搜索(03) → DP(04 基础)	2 周
LeetCode 玩家	DP(04) → 图论(02) → 数论(05)	3 周
ACM 入门	图论(02) → DP(04 进阶) → 组合(06) → 计算几何(07)	6 周
冲奖选手	全部模块，重点攻克网络流、计算几何、生成函数	12 周