Rusty 算法和数据结构用于教育和 LeetCode 解决方案

此仓库展示了常见算法和数据结构的 Rust 实现，其中大部分基于 William Fiset 的 Java 实现：https://github.com/williamfiset/Algorithms。我强烈推荐他的 YouTube 频道https://www.youtube.com/user/purpongie，他在那里使用插图、动画和伪代码详细解释了许多算法。

除了实现 W. Fiset 的算法外，我还编写了解决竞赛编程问题的解决方案。一些代表性问题在 src/problems 中解释，还有一个 leetcode 文件夹用于我的 LeetCode 解决方案。两者都远未完成。

用法

实现细节在注释和文档中解释，示例用法在单元测试中暗示。要运行测试

cargo test

我在文档中使用 LaTeX 编写一些数学表达式。为了在文档中正确渲染它们，请运行

RUSTDOCFLAGS="--html-in-header katex-header.html" cargo doc --no-deps --open

或此命令的别名

./doc

推荐环境

• 编辑器：Visual Studio Code
  • 扩展：rust-analyzer

这个简单的设置提供了大多数 decent IDE 都会提供的功能（重要的是跳转到定义和类型标记）

内容

图

图表示

• 邻接矩阵（加权和非加权）
• 邻接表（加权和非加权）
• 浓缩邻接矩阵（加权）

基本图算法

• 深度优先搜索（迭代和递归）
• 广度优先搜索（迭代）

树算法

• 树表示：是否包含指向父指针
• 基础知识（DFS、树高、树和等）
• 树中心
• 树根
• 树同构
• 最近公共祖先（LCA）

最小生成树/森林

• 普里姆算法
• 克鲁斯卡尔算法

网络流

• 福特-富克森 + DFS
• DFS 带容量缩放
• Edmonds-Karp 算法（BFS）
• Dinic 算法（BFS + DFS）

最短路径

• BFS（非加权）
• 带拓扑排序的有向图最短路径
• 迪杰斯特拉算法（非负权重，SSSP）
• 贝尔曼-福特算法（SSSP）
• 弗洛伊德-沃舍尔算法（APSP）

其他

• 二分图检查
• 有向无环图图的拓扑排序和最短路径
• 欧拉路径/回路
• 强连通分量（Tarjan算法）

数据结构

• 位操作
• 优先队列（二叉堆）
• 平衡树
  • AVL树
• 并查集（集合归并）
• 稀疏表（范围查询）（通用）

机器学习

聚类

• 层次聚类

数学

• 最大公约数/最小公倍数
• log2

问题

动态规划

• 编辑距离
• 背包问题0/1

回溯法

• 数独
• N皇后问题

图

• 旅行商问题（暴力破解与DP）

网络流

• 老鼠和猫头鹰