Way-to-Algorithm: A C++ repository from xcldswz

Way to Algorithm - 算法之路

Computer Basic Algorithm Tutorial and Source Code - 计算机基础算法教程与源码

Content - 目录

Chapter-1 - Sort - 排序
Chapter-2 - Search - 搜索
Chapter-3 - DataStructure - 数据结构
1. Introduction-ClassicDataStructure - 经典数据结构介绍
2. HashTable - 哈希表
3. DisjointSet - 并查集
4. BinaryIndexTree - 树状数组
5. SegmentTree - 线段树
6. LeftistTree - 左偏树
7. PrefixTree - 前缀树
8. SuffixTree - 后缀树
9. AVLTree - 平衡二叉树
10. RedBlackTree - 红黑树
Chapter-4 - DynamicProgramming - 动态规划 0. Introduction-DynamicProgramming - 动态规划介绍
1. LinearDP - 线性动态规划
  1. LongestCommonSubsequence - 最长公共子序列
  2. LongestIncreasingSubsequence - 最长递增子序列
  3. LongestIncreasingSubsequenceExtension - 最长递增子序列扩展
  4. BidirectionSubsequence - 双向子序列
2. KnapsackDP - 背包问题
  1. ZeroOneKnapsack - 01背包
  2. ZeroOneKnapsackExtension - 01背包扩展
  3. CompleteKnapsack - 完全背包
  4. TwoDimensionKnapsack - 二维背包
  5. GroupKnapsack - 分组背包
3. RegionDynamic - 区域动态规划
  1. MinimumMergeCost - 最小合并代价
  2. MinimumMergeExtension - 最小合并扩展
  3. MaximumBinaryTreeMerge - 最大二叉树合并
4. TreeDynamic - 树形动态规划
  1. BinaryTreeDP - 二叉树动规
  2. MultipleTreeDP - 多叉树动规
  3. MultipleTreeExtension - 多叉树动规问题扩展
  4. LoopedMultipleTreeDP - 带环多叉树动规
  5. TraverseTreeDP - 遍历多叉树动规
Chapter-5 - GraphTheory - 图论
1. Traverse - 遍历
  1. PreorderTraverseBinaryTree - 先序遍历二叉树
  2. InorderTraverseBinaryTree - 中序遍历二叉树
  3. PostorderTraverseBinaryTree - 后先序遍历二叉树
  4. LevelorderTraverseBinaryTree - 层序遍历二叉树
  5. DepthFirstSearch - 深度优先遍历
  6. BreadthFirstSearch - 广度优先遍历
  7. TopologicalSort - 拓扑排序
  8. EulerLoop - 欧拉回路
  9. HamiltonLoop - 汉密尔顿回路
  10. Kosaraju - Kosaraju算法
  11. 2-Satisfiability - 2-SAT问题
2. Tarjan - Tarjan算法
  1. StrongestConnectedComponent - 强连通分支
  2. Gabow - Gabow算法
  3. Cut - 割
  4. DoubleConnectedComponent - 双连通分支
  5. LeastCommonAncestor - 最近公共祖先
  6. RangeExtremumQuery - 区域最值查询
3. MinimumSpanningTree - 最小生成树
  1. Kruskal - Kruskal算法
  2. Prim - Prim算法
  3. SecondMinimumSpanningTree - 次小生成树
  4. DegreeBoundedSpanningTree - 度限制生成树
  5. OptimalRatioSpanningTree - 最优比率生成树
4. ShortestPath - 最短路径
  1. Relaxation - 松弛操作
  2. BellmanFord - BellmanFord算法
  3. ShortestPathFasterAlgorithm - SPFA最短路径更快算法
  4. Dijkstra - Dijkstra算法
  5. Floyd - Floyd算法
  6. DifferentConstraints - 差分约束
5. FlowNetwork - 网络流
  1. EdmondsKarp - EdmondsKarp算法
  2. PushAndRelabel - 压入与重标记
  3. Dinic - Dinic算法
  4. DistanceLabel - 距离标号算法
  5. RelabelToFront - 重标记与前移算法
  6. HighestLabelPreflowPush - 最高标号预留与推进算法
  7. DistanceLabel_AdjacentListVersion - 距离标号算法_邻接表优化版
  8. DistanceLabel_AdjacentListVersion - 距离标号算法_邻接表优化版
  9. Summary-Maxflow - 最大流算法小结
  10. MinimumCost_Maxflow - 最小费用最大流
  11. MultipleSourceSink_Maxflow - 多源点、多汇点最大流
  12. Connectivity - 连通度
  13. NoSource_NoSink_VolumeBounded_Flow - 无源点、无汇点、容量有上下界的流网络
  14. VolumeBounded_Maxflow - 容量有上下界的最大流
  15. VolumeBounded_Minflow - 容量有上下界的最小流
6. BinaryMatch - 二分匹配
  1. Hungarian - 匈牙利算法
  2. HopcroftKarp - Hopcroft-Karp算法
  3. Match2Maxflow - 二分匹配转最大流
  4. KuhnMunkres - Kuhn-Munkres算法
  5. Introduction-Domination_Independent_Covering_Clique - 支配集，独立集，覆盖集与团的介绍
  6. WeightedCoveringAndIndependentSet - 最小点权覆盖和最大点权独立集
  7. MinimumDisjointPathCovering - 最小不相交路径覆盖
  8. MinimumJointPathCovering - 最小可相交路径覆盖
  9. Coloring - 染色问题
Chapter-6 - BasicCalculation - 基本计算
1. LargeNumberCalculation - 大数字计算
2. DecimalConversion - 数字进制转换
3. Exponentiation - 幂运算
Chapter-7 - CombinatorialMathematics - 组合数学
1. Introduction-CombinatorialMathematics - 组合数学介绍
2. FullPermutaion - 全排列
3. Combination - 组合
4. Permutaion - 排列
5. PermutationGroup - 置换群
6. Catalan - 卡特兰数
Chapter-8 - NumberTheory - 数论
1. Sieve - 筛选算法
2. Euclid - Euclid算法
3. EuclidExtension - Euclid扩展
4. ModularLinearEquation - 模线性方程
5. ChineseRemainerTheorem - **剩余定理
6. ModularExponentiation - 模幂运算
Chapter-9 - LinearAlgebra - 线性代数
1. Matrix - 矩阵
  1. Strassen - Strassen算法
  2. GaussElimination - 高斯消元法
  3. LUP - LUP分解
  4. InverseMatrix - 矩阵求逆
2. LinearProgramming - 线性规划
  1. Simplex - 单纯形算法
  2. Dinkelback - Dinkelbach算法
Chapter-10 - AnalyticGeometry - 解析几何
1. VectorAndPolygon - 向量与多边形
  1. Cross - 叉积
  2. SegmentIntersection - 线段相交
  3. PointInConvexPolygon - 点在凸多边形内
  4. Sweeping - 扫除算法
  5. ConvexPolygonArea - 凸多边形面积
  6. ConvexPolygonGravityCenter - 凸多边形重心
  7. RayDistinguish - 射线判别
  8. RotatingCalipers - 旋转卡壳
2. ConvexHull - 凸包
  1. NearestNeighbor - 最近点对
  2. GrahamScan - Graham扫描
  3. QuickConvexHull - 快速凸包算法
Chapter-11 - StringMatch - 字符串匹配
1. NaiveStringMatch - 简单字符串匹配
2. KnuthMorrisPratt - KMP算法
3. TrieTree - 字典树
4. AhoCorasickAutomation - AC自动机
Chapter-12 - GameTheory - 博弈论
1. BashGame - 巴什博弈
2. WythoffGame - 威佐夫博奕
3. NimGame - 尼姆博弈
4. SpragueGrundy - SG函数

Introduction - 内容概要

这是一本关于大学生计算机算法的书籍。之所以称之为“书”而不是“源码”，是因为我发现单纯的代码很难让人学习和理解，我自己在学习的过程中走了不少的弯路。我认为将算法图形化、公式化是最容易让人学习和理解的方式，这样可以从数学角度来准确的描述问题和解法。因此我将这些内容用自己的方式画出来，配合代码和测试，希望给出一个比较令人满意的讲解。
本书的每一章专门讲解一类算法问题，其中又划分多个小节，专门讲解其中的一个分支或变种。同一章节中各个小节之间会有明显的联系，基础的算法在前面，变种的、高级的算法在后面。每个算法都有讲解、源码和测试三个部分。在编写的过程中，我学习和参考了非常多的资料，有很多都忘记了，记得的我会列在参考资料中。
后来NEWPLAN同学参加到这本书籍的编写中，他添加了很多内容，我们也欢迎更多的同学来一起丰富这些资料，不过有的时候我会调整一下代码规范，这是为了方便阅读。

作者：NEWPLAN，林荣彬

西安交通大学计算机系
林荣彬
2014年2月16日

xcldswz/Way-to-Algorithm

Way to Algorithm - 算法之路

Content - 目录

Introduction - 内容概要

Reference - 参考资料