##

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   广度优先搜索

  • BidirectionpeadthSearch   双向优先搜索

  • 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   双向子序列

  • Pack   背包问题
    • ZeroOnePack   01背包

    • ZeroOnePackPath   01背包路径

    • CompletePack   完全背包

    • MultiplePack   多重背包

    • TwoDimensionPack   二维背包

    • PacketPack   分组背包

    • GenericItem   泛化物品

    • DependentPack   依赖背包

  • RegionDynamic   区域动态规划
    • MinimumMergeCost   最小合并代价

    • MinimumMergeExtension   最小合并扩展

    • MaximumBinaryTreeMerge   最大二叉树合并

  • TreeDynamic   树形动态规划
    • BinaryTree   二叉树

    • MultipleTree   多叉树

    • Multiple2BinaryTree   多叉树转二叉树

    • MultipleTreePath   多叉树路径

    • LoopedMultipleTree   带环多叉树

    • MultipleTreeTraverse   多叉树遍历

• 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函数

========================================

阅读方法

本书的每一章专门讲解一类算法问题，其中又划分多个小节，专门讲解某一分支或变种问题。 同一章节中各个小节之间会有明显的联系，简单的算法在前面，复杂的算法在后面。 每个算法都有讲解、源码和测试三个部分。

========================================

西安交通大学计算机系

林荣彬

2014年2月16日