如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。
A. 完全图 B. 连通图 C. 有回路 D. 一棵树
N诺智能批改可自动批改答案并给出反馈，每次使用将消耗 1个诺币
您当前的诺币数量： 个
N诺正在智能批改，预计需要30秒，请稍候...
深度优先搜索（DFS）是一种图遍历算法，它从一个顶点开始，尽可能深地搜索图的分支。如果在一次DFS中可以访问图的所有顶点，这意味着从任一顶点出发，都可以到达图中的所有其他顶点。
对于各个选项来说：
A. 完全图：完全图是指图中任意两个顶点之间都有边相连的图。虽然完全图可以通过DFS访问所有顶点，但这并不是唯一满足条件的图。
B. 连通图：连通图是指图中任意两个顶点之间都存在路径的图。如果一个图是连通的，那么从任一顶点出发进行DFS确实可以访问所有顶点。
C. 有回路：有回路并不保证从任一顶点出发进行DFS可以访问所有顶点。一个有回路的图可能是非连通的。
D. 一棵树：树是一种特殊的连通无环图。如果一个图是一棵树，那么从任一顶点出发进行DFS可以访问所有顶点，因为树是连通的且没有回路。
综上，如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是连通图，但不一定是完全图。
故而答案选B。
A怎么不对呀？任意两顶点都有边那么肯定是连通是呀。
快乐小土狗 回复 小叶子： 不是任意两顶点都有边，而是任意两个顶点有路径，比如其中一种情况是树。
小叶子 回复 小叶子： 我看书的定义完全图就是任意两个顶点都有边。完全图肯定是连通的，所以感觉深度遍历一次就能遍历完全部顶点啊！！
快乐小土狗 回复 小叶子： 你的逻辑颠倒了，完全图确实可以推出深度遍历一次就能遍历完全部顶点，但是题目问的是深度遍历一次就能遍历完全部顶点的图一定是什么图。
快乐小土狗 回复 小叶子： 简单点说就是，完全图一定是连通的，但是连通的不一定是完全图，一定是连通图。
完全图：任意两个顶点存在边
连通图：任意两个顶点有路径/连通
B
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案