内容发布更新时间 : 2024/5/16 17:48:59星期一 下面是文章的全部内容请认真阅读。

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