4.4 图的基本应用及其复杂度分析

4.4 图的基本应用及其复杂度分析

　　考试大纲涉及本节的知识点有：最小生成树定义、最短路径、拓扑排序和关键路径。

一、选择题

　　1．选择题题目部分
　　● 数据结构中的迪杰斯特拉（Dijkstra）方法是用来求 （1） 。
　　（1）A．关键路径 B．最短路径 C．拓扑排序 D．字符串匹配
　　● 关键路径是指AOE网中 （2） 。
　　（2）A．从开始节点到完成节点的最长的路径 B．最长的回路
　　C．从开始节点到完成节点的最短的路径 D．最短的回路
　　● 判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用 （3） 。
　　（3）A．求关键路径的方法 B．求最短路径的Dijkstra方法
　　C．深度优先遍历算法 D．广度优先遍历算法
　　● 设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为 （4） 。
　　（4）A．O(n ) B．O(en) C．O(e ) D．O(n+e)
　　● 以下哪个是有向图图4-10的拓扑排序序列 （5） 。                                                                              
　　（5）A．ABCDE B．ACDEB C．ABDCE D．ACBED
　　● 图4-10所示的有向图所有拓扑排序序列有 （6） 个。
    
　　（6）A．2 B．4 C．6 D．7 
　　● 下列关于AOE网的叙述中，不正确的是 （7） 。
　　（7）A．关键活动不按期完成就会影响整个工程的完成时间
　　B．任何一个关键活动提前完成，那么整个工程将会提前完成
　　C．所有的关键活动提前完成，那么整个工程将会提前完成
　　D．某些关键活动提前完成，那么整个工程将会提前完成
　　●（a）求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义。
　　（b）利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)（图用邻接矩阵表示）。
　　（c）Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。
　　上面说法不正确的是 （8） 。
　　（8）A．（a），（b），（C） B．（a） C．（a），（c） D．（b），（c）
　　 2．选择题练习答案与分析
　　题号（1）
　　答案 B
　　习题分析：
　　迪杰斯特拉（Dijkstra）算法是求图中某一顶点到其他各顶点最短路径的算法。
　　题号（2）
　　答案 A
　　习题分析：
　　关键路径是指AOE网中从开始点到完成点的最长路径的长度，所谓路径的长度是指该条路径上所有弧的权值之和，而不是路径的数量。
　　题号（3）
　　答案 C
　　习题分析：
　　除了拓扑排序可以用来判断有向图是否有回路外，利用图的深度优先遍历方法，也可以判断图中是否有回路。
　　题号（4）
　　答案 D
　　习题分析：
　　对于有n个顶点和e条边的有向图而言，若该图无环，根据拓扑排序算法，则每个顶点进一次栈，出一次栈，入度减1的操作在循环语句处要执行e次。因此，总的时间复杂度为O(n+e)。
　　题号（5）
　　答案 A
　　习题分析：
　　拓扑排序不改变顶点之间的前后关系，在图4-10中存在以下关系：
　　（1）A≤B、C、D、E （2）B≤D、E （3）C≤D、E （4）D≤E
　　其中“A≤B”表示A领先于B，即在拓扑排序序列中，A处于B之前。
　　选项B中，D≤B、E≤B，不正确；
　　选项C中，D≤C，不正确；
　　选项D中，E≤D ，不正确。
　　因此，答案 为A。
　　题号（6）
　　答案 A
　　习题分析：
　　观察图4-10所示有向图，其拓扑排序序列，有如下规定：
　　（1）A必须是序列第一个元素；（2）E必须是序列最后一个元素；（3）D必须是序列倒数第二个元素。即序列形如：A??DE，其中?为B或D，所以共两种拓扑排序序列。
　　题号（7）
　　答案 B
　　习题分析：
　　对于关键路径，需要牢记以下两点。
　　（1）关键路径上所有的活动都是关键活动。因此提前完成非关键活动并不能加快工程的速度。
　　（2）网络中的关键路径并不唯一，对于有几条关键路径的网来说，仅仅提高某一条关键路径上关键活动的速度，是不能缩短整个工程工期的，而必须同时提高几条关键路径上关键活动的速度。
　　所以，并不是网中任何一个关键活动的提前完成，整个工程都能提前完成。
　　题号（8）
　　答案 C
　　习题分析：
　　分别对各个选项做出分析：
　　（a）最短路径算法要求网中弧的权值必须为正数，但是在Dijsktra算法中，权值不能为负的，并不是因为在实际应用中无意义，而是算法本身的适应条件不允许权值为负数。所以（a）错误。
　　（b）重复利用Dijsktra算法n次即可求得每一对不同顶点间的最短路径，Dijsktra算法的时间复杂度为O(n2)，那么对此算法执行n次的时间复杂度为O(n3)。所以（b）正确。
　　（c）由对（a）的分析可知，（c）错误。
　　3．训练自测表（如表4-7所示）
 

表4-7  应用题练习自测表