下列关于图的叙述中,正确的是()
A. 有向图必定存在入度为 0 的顶点
B. 有向无环图的拓扑排序有序序列存在且唯一
C. 各顶点的度均大于等于 2 的无向图必有回路
D. 可用 BFS 算法求出带权图中的每一对顶点的最短路径
下面对各选项进行分析:
选项...
用户登录可进行刷题及查看答案
选项 A
分析:有向图不一定存在入度为 0 的顶点。比如一个有向环,像顶点 A 指向顶点 B,顶点 B 指向顶点 C,顶点 C 又指向顶点 A,在这个有向环中,每个顶点的入度都为 1,不存在入度为 0 的顶点。所以该选项错误。
选项 B
分析:有向无环图(DAG)的拓扑排序序列不一定唯一。当图中存在多个入度为 0 的顶点时,选择不同的顶点作为起始点,就会得到不同的拓扑排序序列。例如,有一个有向无环图,顶点 A 和顶点 B 的入度都为 0,若先选 A 进行拓扑排序和先选 B 进行拓扑排序,得到的序列是不同的。所以该选项错误。
选项 C
分析:在无向图中,如果各顶点的度均大于等于 2,那么该图必定存在回路。可以用反证法来证明,假设图中没有回路,那么这个图就是一个森林(由若干棵树组成)。而树的性质是边数等于顶点数减 1,并且树中至少有两个度为 1 的顶点(叶子节点),这与 “各顶点的度均大于等于 2” 相矛盾。所以该选项正确。
选项 D
分析:BFS(广度优先搜索)算法适用于无权图中求单源最短路径,因为在无权图中,顶点之间的边权默认是相等的,BFS 可以按照层次遍历的方式找到最短路径。但对于带权图,边权可能各不相同,BFS 无法考虑边权的差异,不能求出带权图中每一对顶点的最短路径。例如,在一个带权图中,可能存在一条边权较小但路径较长的路径,BFS 可能会忽略这条路径而选择层次更浅但边权更大的路径。求带权图中每一对顶点的最短路径,通常需要使用 Floyd - Warshall 算法等专门处理带权图最短路径问题的算法。所以该选项错误。
正确答案:C
登录后提交答案
暂无评论,来抢沙发