2. 考研
  3. 如果从无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( )。

如果从无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( )。

admin2019-12-10  79
问题 如果从无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是(    )。
选项 A、完全图
B、连通图
C、有回路
D、一棵树
答案B
解析 图的一次深度优先搜索遍历，可以遍历完图中一个连通分量中所有的顶点。如果图是连通的，则图只含有一个连通分量，即图本身，这样一次深度优先搜索遍历即可遍历完图中所有顶点。因此本题选B。完全图相当于在连通图上加上了更严格的条件，即任意两个顶点间都存在边，对于满足本题的要求不需要完全图，条件达到连通图的强度就足够了。
    可能疑问点：有些考生可能认为D也正确，树难道不是连通图吗?
   提示：树的类型有很多，相信选D的同学必定是思维定式，总是想着普通的无向树，这些树当然是连通图。但是，是否想过有向树?想必提到这个概念误选D的考生就会恍然大悟了，不再多做解释。
    补充：用深度优先算法遍历一个无环有向图，并在深度优先退栈返回时打印相应的顶点，则输出的顶点序列是逆拓扑有序。
转载请注明原文地址:https://www.kaotiyun.com/show/Wm3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)