BFS 糟糕的复杂性
BFS bad complexity
我正在使用邻接列表来表示 OCaml 中的图形。然后我在 OCaml 中从节点 s
.
开始实现了以下 BFS
let bfs graph s=
let size = Array.length graph in
let seen = Array.make size false and next = [s] in
let rec aux = function
|[] -> ()
|t::q -> if not seen.(t) then begin seen.(t) <- true; aux (q@graph.(t)) end else aux q
in aux next
size
表示图的节点数。 seen
是一个数组,其中 seen.(t) = true
如果我们已经看到节点 t
,next
是我们需要看到的节点的列表。
问题是通常 BFS 的时间复杂度是线性的 (O( V + E)) 但我觉得我的实现没有这种复杂度。如果我没记错的话,q@graph.(t)
的复杂度相当大,因为它是 O(| q |)。所以我的复杂性非常糟糕,因为在每一步我都要连接两个列表,而且时间很长。
因此我想知道如何调整此代码以制作高效的 BFS?问题(我认为)来自使用列表的队列的实现。 OCaml 中 Queue 模块的复杂性是否需要 O(1) 添加一个元素?在这种情况下,我如何使用这个模块来使我的 bfs 工作,因为我不能像列表一样轻松地与队列进行模式匹配?
the complexity of q@graph.(t) is quite big since it's O(| q |). So my complexity is quite bad since at each step I am concatenating two lists and this is heavy in time.
你完全正确——这是你 BFS 的瓶颈。你应该很高兴能够使用 Queue
模块,因为根据 https://ocaml.org/learn/tutorials/comparison_of_standard_containers.html 插入和获取元素的操作是 O(1)。
OCaml 中队列和列表的区别之一是队列是可变结构,因此您需要使用非纯函数,例如 add
、take
和 top
分别就地插入元素,从前面弹出元素和return第一个元素。
If I am not mistaken the complexity of q@graph.(t) is quite big since it's O(| q |).
确实是这个问题。你应该使用的是 graph.(t) @ q
。其复杂度为 O(| graph.(t) |).
您可能会问:这有什么区别?
区别在于|q|可以是从 0 到 V * E.graph.(t) 的任何值,另一方面您可以使用。您最多访问图中的每个顶点一次,因此总体复杂度为
O(\Sum_V |grahp.(v))
图中每个顶点的所有边的总和。或者换句话说:E.
这使您了解 O(V + E) 的整体复杂性。
我正在使用邻接列表来表示 OCaml 中的图形。然后我在 OCaml 中从节点 s
.
let bfs graph s=
let size = Array.length graph in
let seen = Array.make size false and next = [s] in
let rec aux = function
|[] -> ()
|t::q -> if not seen.(t) then begin seen.(t) <- true; aux (q@graph.(t)) end else aux q
in aux next
size
表示图的节点数。 seen
是一个数组,其中 seen.(t) = true
如果我们已经看到节点 t
,next
是我们需要看到的节点的列表。
问题是通常 BFS 的时间复杂度是线性的 (O( V + E)) 但我觉得我的实现没有这种复杂度。如果我没记错的话,q@graph.(t)
的复杂度相当大,因为它是 O(| q |)。所以我的复杂性非常糟糕,因为在每一步我都要连接两个列表,而且时间很长。
因此我想知道如何调整此代码以制作高效的 BFS?问题(我认为)来自使用列表的队列的实现。 OCaml 中 Queue 模块的复杂性是否需要 O(1) 添加一个元素?在这种情况下,我如何使用这个模块来使我的 bfs 工作,因为我不能像列表一样轻松地与队列进行模式匹配?
the complexity of q@graph.(t) is quite big since it's O(| q |). So my complexity is quite bad since at each step I am concatenating two lists and this is heavy in time.
你完全正确——这是你 BFS 的瓶颈。你应该很高兴能够使用 Queue
模块,因为根据 https://ocaml.org/learn/tutorials/comparison_of_standard_containers.html 插入和获取元素的操作是 O(1)。
OCaml 中队列和列表的区别之一是队列是可变结构,因此您需要使用非纯函数,例如 add
、take
和 top
分别就地插入元素,从前面弹出元素和return第一个元素。
If I am not mistaken the complexity of q@graph.(t) is quite big since it's O(| q |).
确实是这个问题。你应该使用的是 graph.(t) @ q
。其复杂度为 O(| graph.(t) |).
您可能会问:这有什么区别?
区别在于|q|可以是从 0 到 V * E.graph.(t) 的任何值,另一方面您可以使用。您最多访问图中的每个顶点一次,因此总体复杂度为
O(\Sum_V |grahp.(v))
图中每个顶点的所有边的总和。或者换句话说:E.
这使您了解 O(V + E) 的整体复杂性。