25版王道数据结构课后习题详细分析第六章图 6.4图的应用

一、单项选择题

————————————————————

解析：

当无向连通图存在权值相同的多条边时，最小生成树可能是不唯一的;另外，由于这是一个无向连通图，因此最小生成树必定存在，从而选A。

正确答案：

————————————————————

解析：

因为无向连通图的最小生成树不一定唯一，所以用不同算法生成的最小生成树可能不同，但当无向连通图的最小生成树唯一时，不同算法生成的最小生成树必定是相同的。

正确答案：

————————————————————

解析：

最小生成树算法是基于贪心策略的，每次总是选取权值最小且满足条件的边，若各边权值不同，则每次选择的新顶点也是唯一的，因此最小生成树唯一，A正确。对于B，若无向图本身就是一棵树，则最小生成树就是它本身，这时就是唯一的。对于C，选取的n-1条边可能构成回路。对于D，含有n个顶点、n-1条边的子图可能构成回路，也可能不连通。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

U={1,2,3}，v-U= {4,5,…}，候选边只能是这两个顶点集之间的边，只有A符合题意。

正确答案：

————————————————————

解析：

若选取边(1,3)则会构成回路。

正确答案：

————————————————————

解析：

A正确，见严蔚敏撰写的教材《数据结构》。Dijkstra算法适合求解有回路的带权图的最短路径，也可以求任意两个顶点的最短路径，不适合求带负权值的最短路径问题。在用Floyd算法求两个顶点的最短路径时，当最短路径发生更改时，pathk-1就不是pathk的子集。
正确答案：

————————————————————

解析：在负权图中，Dijkstra 算法既不能保证每次选出的顶点都是真正的最近顶点，又不能保证已

确定的最短路径不再被改变，因此 Dijkstra算法不允许边的权为负，Ⅰ正确。求每对顶点间的最短路径需要调用Dijkstra算法n次，时间复杂度为O(n^3)，I错误。Floyd算法求每对顶点间的最短路径允许有负边存在，但不允许有包含负边组成的回路，Ⅲ正确。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：在 Dijkstra算法的执行过程中，只可能修改从源点О到集合V-S中某个顶点的最短路径。

正确答案：

————————————————————

解析：使用深度优先遍历，若从有向图上的某个顶点u出发，在 DFS(u)结束之前出现一条从顶点v到u的边，由于v在生成树上是u的子孙，图中必定存在包含u和v的环，因此深度优先遍历可以检测一个有向图是否有环。拓扑排序时，当某顶点不为任何边的头时才能加入序列，存在环时环中的顶点一直是某条边的头，不能加入拓扑序列。也就是说，还存在无法找到下一个可以加入拓扑序列的顶点，则说明此图存在回路。求最短路径是允许图有环的。至于关键路径能否判断一个图有环，则存在一些争议。关键路径本身虽然不允许有环，但求关键路径的算法本身无法判断是否有环，判断是否有环是求关键路径的第一步——拓扑排序。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

强连通图是指有向图中任意顶点对之间都存在两条相反的路径，这意味着强连通图中一定存在环，因此不能进行拓扑排序，Ⅰ正确。假设顶点a和b的入度均为0，且分别有两条孤从a和b指向同一顶点c，则产生的拓扑序列可以是abc，但是此时并无一条弧<a, b>，Ⅱ错误。

正确答案：

————————————————————

解析：一个有向图中的顶点不能排成一个拓扑序列，表明其中存在一个顶点数目大于1的回路(环)、该回路构成一个强连通分量，从而答案选D。

正确答案：

————————————————————

解析：本图的拓扑排序序列有ABCFDEG,ABCDFEG,ABCDEFG,ABDCFEG和 ABDCEFG。读者应能把这一类经典习题的拓扑序列全部写出来。

正确答案：

————————————————————

解析：拓扑序列的过程:找到入度为О的顶点，删除该顶点及其所有出边，并将顶点加入拓扑序列，重复直至所有顶点都加入拓扑序列。选择入度为О的顶点v，删除与v有关的边;此时顶点v的入度为0，选择v，删除与v有关的边;以此类推，得出G的拓扑序列。

正确答案：

————————————————————

解析：无向图的邻接矩阵存储中，每条边存储两次,且A[i][j]=A[j][i]。

正确答案：

————————————————————

解析：此题一直以来争议较大，因为有些书中漏掉了“有序”二字。可以证明，对有向图中的顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元素全为零的充分必要条件是，该有向图可以进行拓扑排序。若这个题目把“有序”二字去掉，显然应选D。但此题题干中已经指出是“有序的拓扑序列"，因此应选C。需要注意的是，若一个有向图的邻接矩阵为三角矩阵（对角线以上或以下的元素为O)，则图中必不存在环，因此其拓扑序列必然存在。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：观察题图，从V到V的最长路径为V0-V1-V4-V6-V8，长度为6＋1+9+2=18。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

一个事件的最迟发生时间=min{以该事件为尾的弧的活动的最迟开始时间}，或min{以该事件为尾的弧所指事件的最迟发生时间与该弧的活动的持续时间之差}。改变AOE网中任何一个活动的持续时间，需要重新计算关键活动，可能导致关键路径的改变。

正确答案：

————————————————————

解析：

若改变的是所有关键路径上的公共活动，则不一定会产生不同的关键路径（延长必然不会导致，只有缩短才有可能导致)。根据关键路径的定义，可知选项Ⅱ正确。关键路径是源点到终点的最长路径，只有所有关键路径的长度都缩短时，整个图的关键路径才能有效缩短，但也不能任意缩短，一旦缩短到一定程度，该关键活动就可能变成非关键活动。

正确答案：

————————————————————

解析：邻接矩阵第i列值全为oo，说明顶点i没有入边，为整个工程的开始，若关键路径存在，则该顶点一定是起点。不能确定关键路径是否存在，也不能确定其对应的无向图的连通分量个数。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：最小生成树的树形可能不唯一（因为可能存在权值相同的边)，但代价一定是唯一的，选项Ⅰ正确。若权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，选项П错误。设N个结点构成环，N-1条边权值相等，另一条边权值较小，则从不同的顶点开始 Prim 算法会得到N-1种不同的最小生成树，选项错误。当最小生成树唯一时(各边的权值不同)，Prim算法和Kruskal算法得到的最小生成树相同，选项Ⅳ错误。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：找出AOE网的全部关键路径为bdcg、bdeh和 bfh。根据性质，只有当所有关键路径的活动时间同时减少时，才能缩短工期。即正确选项中的路径必须能涵盖所有的关键路径。选项A和B不能涵盖bfh这条路径，选项C不能涵盖bdcg和 bdeh这两条路径，只有选项C能涵盖所有关键路径，因此只有加快f和d的进度才能缩短工期（建议在图中检验)。

正确答案：

————————————————————

解析：按照拓扑排序的算法，每次都选择入度为О的结点从图中删除，此图中一开始只有结点3的入度为0;删除结点3后，只有结点1的入度为0;删除结点1后，只有结点4的入度为0;删除结点4后，结点2和结点6的入度都为0，此时选择删除不同的结点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为3,1,4,2,6,5和3,1,4, 6,2,5，选D。

正确答案：

————————————————————

解析：从V4开始，Kruskal算法选中的第一条边一定是权值最小的(Vi,V4)，选项B错误。由于V和V已经可达，因此含有7和V的权值为8的第二条边一定符合Prim算法，排除A、D。

正确答案：

————————————————————

解析：第一个顶点和最后一个顶点相同的路径称为回路;序列中顶点不重复出现的路径称为简单路径;回路显然不是简单路径，Ⅰ错误。稀疏图是边比较少的情况，邻接矩阵存储的空间复杂度为O(n2)，必将浪费大量的空间，而邻接表存储的空间复杂度为 O(n+e)，所以应选用邻接表，Ⅱ错误。存在回路的有向图不存在拓扑序列，若拓扑排序输出结束后所余下的顶点都有前驱，则说明只得到了部分顶点的拓扑有序序列，图中存在回路，Ⅲ正确。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：采用邻接表作为AOV网的存储结构进行拓扑排序，需要对n个顶点做进栈、出栈、输出各一次，当处理e条边时，需要检测这n个顶点的边链表结点，共需要的时间为O(n + e)。若采用邻接矩阵作为AOV网的存储结构进行拓扑排序，在处理e条边时需对每个顶点检测相应矩阵中的某一行，寻找与它相关联的边，以便对这些边的入度减1，需要的时间代价为O(n')。
【补充】有两种常用的拓扑排序算法:基于 BFS 的算法和基于DFS 的算法。本题未指明采用哪种算法，因此只需验证一种算法即可（说明两种算法在对应条件下的时间复杂度相同）。
基于BFS的算法的思想:首先找到所有入度为0的结点，将它们加入一个队列，并将它们作为拓扑序列的起始部分﹔然后依次从队列中取出结点，并删除它们与后继结点的所有边。若某个后继结点的入度变为0，则将它也加入队列，并将它加入拓扑序列，重复这个过程。
基于DFS的算法的思想:在 DFS调用过程中设定一个时间标记，当 DFS 调用结束时，对各结点计时，进而按结束时间从大到小排序，可以得到一个拓扑序列。

正确答案：

————————————————————

解析：拓扑排序每次选取入度为0的结点输出，经观察不难发现拓扑序列前两位一定是1,5或5, 1(因为只有1和5的入度均为0，且其他结点都不满足仅有1或仅有5作为前驱)。

正确答案：

————————————————————

解析：活动d的最早开始时间等于该活动弧的起点所表示的事件的最早发生时间，活动d 的最早开始时间等于事件2的最早发生时间max {a, +c}=max{3,12}=12。活动d的最迟开始时间等于该活动弧的终点所表示的事件的最迟发生时间与该活动所需时间之差，先算出图中关键路径长度为27（对于不复杂的选择题，找出所有路径计算长度)，那么事件4的最迟发生时间为min{27-g}= min{27-6}=21，活动d的最迟开始时间为21-d =21-7=14。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：根据题干所提供的信息可知:
①图G为有向无环图，因此一定存在拓扑序列和逆拓扑序列。②DFS的性质是顶点v的所有后继顶点y出栈后，v才会出栈。
③本题要求执行输出语句后立刻退出递归，即执行完输出语句后立即出栈，因此后进栈的顶点先输出，结合②不难得出只有输出顶点v的所有后继顶点y后，v才会输出。
综合上述分析，输出的顶点序列是逆拓扑有序序列。

正确答案：

————————————————————

解析：关键路径是指权值之和最大而非边数最多的路径，A错误。选项B是关键路径的概念。无论是存在一条还是存在多条关键路径，增加任意一个关键活动的时间都会延长工程的工期，因为关键路径始终是权值之和最大的那条路径，C错误。仅有一条关键路径时，减少关键活动的时间会缩短工程的工期;存在多条关键路径时，缩短一条关键活动的时间不一定会缩短工程的工期，缩短了路径长度的那条关键路径不一定还是关键路径，D错误。

正确答案：

————————————————————