算法重点整理—rj07
一、算法简介
1、四个渐进符号（O，?，?, o）,前三个比较重要 2、算法的五个特征：
■ 有限性 ■ 确定性 ■ 输入 ■ 输出 ■ 能行性
二、22章—图的基本算法
邻接表 1、熟记图的两种表示法
邻接矩阵 2、习题22.1-6、22.1-7
3、BFS、DFS熟练掌握，不会单考，可能会结合后面应用。 4、各种图算法的O复杂性，在课件上
5、BFS中最短路径的定义，以及引理22.1，22.2，22.3要学会应用。 广度优先树以及路径的打印了解。 6、习题22.2-6（二分图）
7、DFS中定理22.7—括号定理，推论22.8以及定理22.9---白色路径定理会证明。 8、边的分类，知道它们的含义,会应用 9、定理22.10了解证明过程的含义 10、习题22.3-12
11、拓扑排序的思想，是如何用DFS解决的，以及引理22.11和22.12的证明。 12、习题22.4-2，22.4-3
13、基本图算法解强连通分支的思路 三、23章----最小生成树
1、生成树、最小生成树的概念 2、“通用算法”的思想以及里面的轻边、安全边、割的含义。 3、定理23.1的证明。
4、作业题23.1-2，23.1-4，23.1-5要了解
5、考Kruskal和Prim算法两者的不同点和相同点，不会考具体的算法代码、应用。 6、习题23.2-1
7、瓶颈生成树了解就行，23-4其它最小生成树算法 四、24章---单源最短路径 1、不考概念，知道其含义
2、引理24.1，负权边，回路，最短路径表示这四个知识点理解就行。 3、松弛技术要掌握
4、最短路径以及松弛的6个性质要掌握，证明及应用。（具体的证明在后面的24.5节） 5、掌握Bellman-Ford算法，但其正确性证明不考。 6、有向无回路图中的单源最短路径--理解。 7、Djjkstra算法重点理解它的局限性。
8、Djjkstra算法的正确性证明不考，书上最后一段和其它算法的比较比较重要。 9、习题24.3-2和24.3-8
10、差分约束系统一般性理解
五、25章—每对顶点间的最短路径
1、最终结果的表示以及最短路径的打印 2、矩阵相乘法中的slow和faster算法 3、Floyd-Warshall算法要掌握 4、有向图中的传递闭包一般理解 5、稀疏图上的Johnson算法理解就行 六、26章—最大流
1、流网络的定义，容量限制、反对称性、流守恒性 2、网络流的一个例子不用看
3、具有多个源点和多个汇点的网络不考。 4、对流的处理要会。
5、Ford-Fulkerson算法要掌握并且会应用。里面残留网络、增广路径、割的概念以及最
大流最小割定理的证明要掌握。 七、补充---UDC
1、什么是UDC以及UDC中的定理
2、Haffman编码中知道公式的推导过程，重点会计算那个d。 3、Catalan不考。