---

Way to Algorithm - 算法之路

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

---

Content - 目录结构

• Chapter-1 - Sort   排序
  
  • InsertSort   插入排序
    
  • BubbleSort   冒泡排序
    
  • QuickSort   快速排序
    
  • MergeSort   合并排序
    
• Chapter-2 - Search   搜索
  
  • BinarySearch   二分查找法
    
  • BruteForce   暴力枚举
    
  • Resursion   递归
    
  • BreadthFirstSearch   广度优先搜索
    
  • BidirectionalBreadthSearch   双向优先搜索
    
  • AStarSearch   A*搜索
    
  • DancingLinks   舞蹈链
    
  • Introduction-AdvancedSearch   高级搜索介绍
    
• Chapter-3 - DataStructure   数据结构
  
  • Introduction-ClassicDataStructure   经典数据结构介绍
    
  • HashTable   哈希表
    
  • DisjointSet   并查集
    
  • BinaryIndexTree   树状数组
    
  • SegmentTree   线段树
    
  • LeftistTree   左偏树
    
  • PrefixTree   前缀树
    
  • SuffixTree   后缀树
    
  • AVLTree   平衡二叉树
    
  • RedBlackTree   红黑树
    
• Chapter-4 - DynamicProgramming   动态规划
  
  • 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   遍历多叉树动规
      
• Chapter-5 - GraphTheory   图论
  
  • Traverse   遍历
    
    • TraverseTree   遍历树
      
    • 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   染色问题
      
• Chapter-6 - LinearAlgebra   线性代数
  
  • Matrix   矩阵
    
    • Strassen   Strassen算法
      
    • GaussElimination   高斯消元法
      
    • LUP   LUP分解
      
    • InverseMatrix   矩阵求逆
      
  • LinearProgramming   线性规划
    
    • Simplex   单纯形算法
      
    • Dinkelback   Dinkelbach算法
      
• Chapter-7 - Calculation   数学计算
  
  • BasicCalculate   基础计算
    
    • LargeNumber   大数字
      
    • DecimalConversion   数字十进制与其他进制转换
      
    • Exponentiation   幂运算
      
  • CombinatorialMathematics   组合数学
    
    • Introduction-CombinatorialMathematics   组合数学介绍
      
    • FullPermutaion   全排列
      
    • Combination   组合
      
    • PermutationGroup   置换群
      
    • Catalan   卡特兰数
      
  • NumberTheory   数论
    
    • Sieve   筛选算法
      
    • Euclid   Euclid算法
      
    • EuclidExtension   Euclid扩展
      
    • ModularLinearEquation   模线性方程
      
    • ChineseRemainerTheorem   中国剩余定理
      
    • ModularExponentiation   模幂运算
      
• Chapter-8 - AnalyticGeometry   解析几何
  
  • VectorAndPolygon   向量与多边形
    
    • Cross   叉积
      
    • SegmentIntersection   线段相交
      
    • PointInConvexPolygon   点在凸多边形内
      
    • Sweeping   扫除算法
      
    • ConvexPolygonArea   凸多边形面积
      
    • ConvexPolygonGravityCenter   凸多边形重心
      
    • RayDistinguish   射线判别
      
    • RotatingCalipers   旋转卡壳
      
  • ConvexHull   凸包
    
    • NearestNeighbor   最近点对
      
    • GrahamScan   Graham扫描
      
    • QuickConvexHull   快速凸包算法
      
• Chapter-9 - String   字符串
  
  • NaiveStringMatch   简单字符串匹配
    
  • KnuthMorrisPratt   KMP算法
    
  • TrieTree   字典树
    
  • AhoCorasickAutomation   AC自动机
    
• Chapter-10 - GameTheory   博弈论
  
  • BashGame   巴什博弈
    
  • WythoffGame   威佐夫博奕
    
  • NimGame   尼姆博弈
    
  • SpragueGrundy   SG函数
    

---

Introduction - 内容概要

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

作者：
NEWPLAN
林荣彬

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

---

Reference - 参考资料

• 算法导论 Introduction to Algorithms http://ce.bonabu.ac.ir/uploads/30/CMS/user/file/115/EBook/Introduction.to.Algorithms.3rd.Edition.Sep.2010.pdf

• 背包问题九讲 http://love-oriented.com/pack/