算法整理

算法重点整理—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不考。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4