题3

题3

题目

若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点, 则该图一定是 ( ).
A. 强连通图
B. 连通图
C. 有回路
D. 一颗树

分析

任意两个顶点之间有路径，连了一条边，那就说这个图是连通的
如果这个边是双向的，那就是强连通的
从任意结点出发，深搜都可以搜完，我觉得是选A

解

B
强连通图是有向图, 与题意矛盾, A 错误;
对无向连通图做一次深度优先搜索, 可以访问到该连通图的所有顶点, B 正确;
有回路的无向图不一定是连通图, 因为回路不一定包含图的所有结点, 错误;
连通图可能是树,也可能存在环, 错误。