2. 邻接表法
(三) 图的遍历
1. 深度优先搜索
2. 广度优先搜索
(四) 图的基本应用及其复杂度分析
1. 最小(代价)生成树
2. 最短路径
3. 拓扑排序
4. 关键路径
知识点:
1.图的基本概念,包括:图的定义和特点、无向图、有向图、入度、出度、完全图、生成树、
路径长度、回路、(强)连通图、(强)连通分量等概念。掌握与这些概念相联系的相关
计算题。在基本概念中,完全图、连通分量、生成树和邻接点是重点。
2.图的存储形式。图是复杂的数据结构,有顺序和链式两种存储结构 :数组表示法(重点是
邻接矩阵),邻接表与逆邻接表,这两种存储结构对无向图和有向图均使用。
3.熟练掌握图的两种遍历算法:深度遍历和广度遍历。深度遍历和广度遍历是图的两种基本
的遍历算法,这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章
的重要性。
掌握图的两种遍历算法的应用,图一章的算法设计题常常是基于这两种基本的遍历算法而
设计的。例如,在(强)连通图中,主过程一次调用深(广)度优先遍历过程( DFS/
BFS),即可遍历全部顶点,故可以用此方法求出连通分量的个数,要会画出遍历中形成
的深(广)度优先生成树和生成森林。又如,“求最长的最短路径问题”和“判断两顶点间是
否存在长为K的简单路径问题”,就用到了广度遍历和深度遍历算法。
4. 最小生成树的概念。连通图的最小生成树通常是不唯一的,但最小生成树边上的权值之和
是唯一的。掌握最小生成树的构造方法:PRIM算法和KRUSKAL算法,根据这两种算法思
想用图示法表示出求给定网的一棵最小生成树的过程。
5. 拓扑排序是在有向图上对入度(先、后)为零的顶点的一种排序,通常结果不唯一。拓扑
排序有两种方法,一是无前趋的顶点优先算法,二是无后继的顶点优先算法。换句话说,
一种是“从前向后”的排序,一种是“从后向前”排。后一种排序出来的结果是“逆拓扑有序”的。
用拓扑排序和深度优先遍历都可判断图是否存在环路。
6. 关键路径问题是图一章的难点问题。理解关键路径的关键有三个方面:一是何谓关键路径,
二是最早时间的含义及求解方法,三是最晚时间的含义及求解方法。简单地说,最早时间
是通过“从前向后”的方法求的,而最晚时间是通过“从后向前”的方法求解的,并且,要想求
最晚时间必须是在所有的最早时间都已经求出来之后才能进行。熟练掌握求解的过程和步
骤。关键路径问题是工程进度控制的重要方法,具有很强的实用性。理解“减少关键活动时
间可以缩短工期”是指该活动为所有关键路径所共有,且减少到尚未改变关键路径的前提下
有效。