首页 > 试题广场 >

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

[单选题]

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

从根节点开始，沿着树的广度遍历树的节点。如果所有节点均被访问，则算法中止

常采用先进后出的栈来实现算法

空间的复杂度为O(V+E)，因为所有节点都必须被储存，其中V是节点的数量，E是边的数量

时间复杂度为O(V+E)，因为必须寻找所有到可能节点的所有路径，其中V是节点的数量，E是边的数量

推荐

河湖之恋

答案选B。为了让先搜索结点的邻结点也先搜索，只能使用先进先出的队列的思想。宽度优先搜索算法常用于图。

编辑于 2015-02-02 22:00:06 回复(0)

InGodWeTrust

宽度优先遍历用队列，深度优先遍历用栈

发表于 2017-04-09 16:03:44 回复(0)

Darius

要不是B错的太明显。。。。。。

发表于 2015-09-12 22:08:37 回复(1)

克劳德圣兽哈士奇

我觉得C中o(V+E)是用来存储树结构的，广度优先遍历所用的栈空间复杂度应该是O(V)

发表于 2017-10-12 20:50:41 回复(0)

不忘初心qqqq

在广度优先的遍历中每个顶点都要进（出）一次列队且仅仅一下（类似于深度优先遍历的进栈），对于每一个顶点u出列队后,要访问的所有邻接点，时间为o(n),因此我们可知广度优先遍历时间复杂度为o(n2)或o(n+e)

发表于 2016-05-23 20:20:24 回复(0)

想打架的蜜蜂

基本思想： 对于无向连通图，广度优先搜索是从图的某个顶点 v₀ 出发，在访问 v₀ 之后，依次搜索访问 v₀ 的各个未被访问过的邻接点 w₁ ， w₂ ，…。然后顺序搜索访问 w₁ 的各未被访问过的邻接点， w₂ 的各未被访问过的邻接点，…。即从 v₀ 开始，由近至远，按层次依次访问与 v₀ 有路径相通且路径长度分别为 1 ， 2 ，…的顶点，直至连通图中所有顶点都被访问一次。

以邻接表作为存储结构的时候，广度优先搜索遍历图的时间复杂度位O(n+e)

发表于 2015-08-31 20:35:25 回复(0)

烷烃

C选项的BFS空间复杂度应该是O(V)吧？

编辑于 2021-07-08 11:02:42 回复(0)

DukeDuke

深用栈，广用队。

发表于 2020-04-11 13:26:49 回复(0)

该

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Prim最小生成树算法采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。

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