Computer Basic Algorithm Tutorial and Source Code - 计算机基础算法教程与源码
- Chapter-1 - Sort - 排序
- Chapter-2 - Search - 搜索
- Chapter-3 - DataStructure - 数据结构
- Introduction-ClassicDataStructure - 经典数据结构介绍
- HashTable - 哈希表
- DisjointSet - 并查集
- BinaryIndexTree - 树状数组
- SegmentTree - 线段树
- LeftistTree - 左偏树
- PrefixTree - 前缀树
- SuffixTree - 后缀树
- AVLTree - 平衡二叉树
- RedBlackTree - 红黑树
- Chapter-4 - DynamicProgramming - 动态规划
0. Introduction-DynamicProgramming - 动态规划介绍
- LinearDP - 线性动态规划
- LongestCommonSubsequence - 最长公共子序列
- LongestIncreasingSubsequence - 最长递增子序列
- LongestIncreasingSubsequenceExtension - 最长递增子序列扩展
- BidirectionSubsequence - 双向子序列
- KnapsackDP - 背包问题
- ZeroOneKnapsack - 01背包
- ZeroOneKnapsackExtension - 01背包扩展
- CompleteKnapsack - 完全背包
- TwoDimensionKnapsack - 二维背包
- GroupKnapsack - 分组背包
- RegionDynamic - 区域动态规划
- MinimumMergeCost - 最小合并代价
- MinimumMergeExtension - 最小合并扩展
- MaximumBinaryTreeMerge - 最大二叉树合并
- TreeDynamic - 树形动态规划
- BinaryTreeDP - 二叉树动规
- MultipleTreeDP - 多叉树动规
- MultipleTreeExtension - 多叉树动规问题扩展
- LoopedMultipleTreeDP - 带环多叉树动规
- TraverseTreeDP - 遍历多叉树动规
- LinearDP - 线性动态规划
- Chapter-5 - GraphTheory - 图论
- Traverse - 遍历
- PreorderTraverseBinaryTree - 先序遍历二叉树
- InorderTraverseBinaryTree - 中序遍历二叉树
- PostorderTraverseBinaryTree - 后先序遍历二叉树
- LevelorderTraverseBinaryTree - 层序遍历二叉树
- DepthFirstSearch - 深度优先遍历
- BreadthFirstSearch - 广度优先遍历
- TopologicalSort - 拓扑排序
- EulerLoop - 欧拉回路
- HamiltonLoop - 汉密尔顿回路
- Kosaraju - Kosaraju算法
- 2-Satisfiability - 2-SAT问题
- Tarjan - Tarjan算法
- StrongestConnectedComponent - 强连通分支
- Gabow - Gabow算法
- Cut - 割
- DoubleConnectedComponent - 双连通分支
- LeastCommonAncestor - 最近公共祖先
- RangeExtremumQuery - 区域最值查询
- MinimumSpanningTree - 最小生成树
- Kruskal - Kruskal算法
- Prim - Prim算法
- SecondMinimumSpanningTree - 次小生成树
- DegreeBoundedSpanningTree - 度限制生成树
- OptimalRatioSpanningTree - 最优比率生成树
- ShortestPath - 最短路径
- Relaxation - 松弛操作
- BellmanFord - BellmanFord算法
- ShortestPathFasterAlgorithm - SPFA最短路径更快算法
- Dijkstra - Dijkstra算法
- Floyd - Floyd算法
- DifferentConstraints - 差分约束
- FlowNetwork - 网络流
- EdmondsKarp - EdmondsKarp算法
- PushAndRelabel - 压入与重标记
- Dinic - Dinic算法
- DistanceLabel - 距离标号算法
- RelabelToFront - 重标记与前移算法
- HighestLabelPreflowPush - 最高标号预留与推进算法
- DistanceLabel_AdjacentListVersion - 距离标号算法_邻接表优化版
- DistanceLabel_AdjacentListVersion - 距离标号算法_邻接表优化版
- Summary-Maxflow - 最大流算法小结
- MinimumCost_Maxflow - 最小费用最大流
- MultipleSourceSink_Maxflow - 多源点、多汇点最大流
- Connectivity - 连通度
- NoSource_NoSink_VolumeBounded_Flow - 无源点、无汇点、容量有上下界的流网络
- VolumeBounded_Maxflow - 容量有上下界的最大流
- VolumeBounded_Minflow - 容量有上下界的最小流
- BinaryMatch - 二分匹配
- Hungarian - 匈牙利算法
- HopcroftKarp - Hopcroft-Karp算法
- Match2Maxflow - 二分匹配转最大流
- KuhnMunkres - Kuhn-Munkres算法
- Introduction-Domination_Independent_Covering_Clique - 支配集,独立集,覆盖集与团的介绍
- WeightedCoveringAndIndependentSet - 最小点权覆盖和最大点权独立集
- MinimumDisjointPathCovering - 最小不相交路径覆盖
- MinimumJointPathCovering - 最小可相交路径覆盖
- Coloring - 染色问题
- Traverse - 遍历
- Chapter-6 - BasicCalculation - 基本计算
- LargeNumberCalculation - 大数字计算
- DecimalConversion - 数字进制转换
- Exponentiation - 幂运算
- Chapter-7 - CombinatorialMathematics - 组合数学
- Introduction-CombinatorialMathematics - 组合数学介绍
- FullPermutaion - 全排列
- Combination - 组合
- Permutaion - 排列
- PermutationGroup - 置换群
- Catalan - 卡特兰数
- Chapter-8 - NumberTheory - 数论
- Sieve - 筛选算法
- Euclid - Euclid算法
- EuclidExtension - Euclid扩展
- ModularLinearEquation - 模线性方程
- ChineseRemainerTheorem - **剩余定理
- ModularExponentiation - 模幂运算
- Chapter-9 - LinearAlgebra - 线性代数
- Matrix - 矩阵
- Strassen - Strassen算法
- GaussElimination - 高斯消元法
- LUP - LUP分解
- InverseMatrix - 矩阵求逆
- LinearProgramming - 线性规划
- Simplex - 单纯形算法
- Dinkelback - Dinkelbach算法
- Matrix - 矩阵
- Chapter-10 - AnalyticGeometry - 解析几何
- VectorAndPolygon - 向量与多边形
- Cross - 叉积
- SegmentIntersection - 线段相交
- PointInConvexPolygon - 点在凸多边形内
- Sweeping - 扫除算法
- ConvexPolygonArea - 凸多边形面积
- ConvexPolygonGravityCenter - 凸多边形重心
- RayDistinguish - 射线判别
- RotatingCalipers - 旋转卡壳
- ConvexHull - 凸包
- NearestNeighbor - 最近点对
- GrahamScan - Graham扫描
- QuickConvexHull - 快速凸包算法
- VectorAndPolygon - 向量与多边形
- Chapter-11 - StringMatch - 字符串匹配
- NaiveStringMatch - 简单字符串匹配
- KnuthMorrisPratt - KMP算法
- TrieTree - 字典树
- AhoCorasickAutomation - AC自动机
- Chapter-12 - GameTheory - 博弈论
- BashGame - 巴什博弈
- WythoffGame - 威佐夫博奕
- NimGame - 尼姆博弈
- SpragueGrundy - SG函数
这是一本关于大学生计算机算法的书籍。之所以称之为“书”而不是“源码”,是因为我发现单纯的代码很难让人学习和理解,我自己在学习的过程中走了不少的弯路。我认为将算法图形化、公式化是最容易让人学习和理解的方式,这样可以从数学角度来准确的描述问题和解法。因此我将这些内容用自己的方式画出来,配合代码和测试,希望给出一个比较令人满意的讲解。
本书的每一章专门讲解一类算法问题,其中又划分多个小节,专门讲解其中的一个分支或变种。同一章节中各个小节之间会有明显的联系,基础的算法在前面,变种的、高级的算法在后面。每个算法都有讲解、源码和测试三个部分。在编写的过程中,我学习和参考了非常多的资料,有很多都忘记了,记得的我会列在参考资料中。
后来NEWPLAN同学参加到这本书籍的编写中,他添加了很多内容,我们也欢迎更多的同学来一起丰富这些资料,不过有的时候我会调整一下代码规范,这是为了方便阅读。
作者:NEWPLAN,林荣彬
西安交通大学计算机系
林荣彬
2014年2月16日