首页 > 试题广场 >

下列关于树的深度优先搜索算法描述错误的是？

[单选题]

按照某种条件往前试探搜索，如果前进中遭到失败，则退回头另选通路继续搜索，直到找到条件的目标为止。

先访问该节点所有的子节点，遍历完毕后选取它未访问过的子节点重复上述过程，直到找到条件的目标为止。

假设树的顶点数为V，则算法的空间复杂度为O(V)

深度优先算法非常适合使用递归来实现

查看正确选项

美团到店招聘

C难道不也是错误的？DFS的时间复杂度和存储方式有关。如果是邻接矩阵的话，是O(V ^2 )，邻接链表的话则是O(V+e),e是边数。

求解答。

发表于 2017-02-17 20:42:45 回复(3)

牛客-68

B 选项的表述符合广度优先遍历的说法。

发表于 2017-05-16 17:39:50 回复(0)

陳丶奕丶迅

B描述的是bfs算法，也就是广度优先遍历算法。

发表于 2022-07-27 14:36:28 回复(0)

Sc0tt

B选项描述的是BFS

发表于 2018-05-14 14:27:23 回复(0)

YoJay

DFS递归算法，需要借助一个递归工作栈，空间复杂度为O(|V|)

当以邻接矩阵表示时，查找每个顶点的邻接点所需时间为O(|V|)，总的时间复杂度为O(|V|²)

以邻接表表示时，查找所有顶点的邻接点所需时间为O(|E|)，访问顶点所需时间为O(|V|)，此时，总的时间复杂度为O(|V|+|E|)

发表于 2018-04-21 21:15:05 回复(1)

Newbie001

DFS在访问图中某一起点V后，由V出发，访问它的任一邻接顶点w1，再从w1出发，访问与w1邻接但还没访问过的顶点w2，然后从w2出发，进行类似的访问，---如此进行下去，直至到达所有的邻接顶点都被访问过的顶点U为止。

发表于 2016-08-22 22:19:44 回复(0)

牛蜗

是不是错了？A选项讲的是深搜，B选项讲的是广搜啊？为什么选A啊？

发表于 2015-05-05 17:01:13 回复(2)

liberal

按照某种条件往前试探搜索，如果前进中遭到失败（正如老鼠钻迷宫老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到条件的目标为止。

发表于 2014-10-25 00:26:04 回复(0)

提交观点

问题信息

树

上传者：小海豹

难度：

8条回答 335收藏 10188浏览

扫一扫，把题目装进口袋