2011年软考程序员考试复习笔试知识点整理(4)2

 　　7、图

　　1. 图的基本概念：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，(强)连通图，(强)连通分量等概念。

　　2. 图的几种存储形式：邻接矩阵，(逆)邻接表，十字链表及邻接多重表。在考查时，有的学校是给出一种存储形式，要求考生用算法或手写出与给定的结构相对应的该图的另一种存储形式。

　　3. 考查图的两种遍历算法：深度遍历和广度遍历

　　深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于"先序、中序、后序遍历"对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如："求最长的最短路径问题"和"判断两顶点间是否存在长为K的简单路径问题"，就分别用到了广度遍历和深度遍历算法。

　　4. 生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法。

　　考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。

　　5. 拓扑排序问题：

　　拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是"从前向后"的排序，一种是"从后向前"排。当然，后一种排序出来的结果是"逆拓扑有序"的。

　　6. 关键路径问题：

　　这个问题是图一章的难点问题。理解关键路径的关键有三个方面：

　　一是何谓关键路径;

　　二是最早时间是什么意思、如何求;

　　三是最晚时间是什么意思、如何求。

　　简单地说，最早时间是通过"从前向后"的方法求的，而最晚时间是通过"从后向前"的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。

　　在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为0。关键路径问题是工程进度控制的重要方法，具有很强的实用性。

　　7. 最短路径问题：

　　与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径(单源最短路径);二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法，注意区分。