BFS 糟糕的复杂性

Question

我正在使用邻接列表来表示 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 工作，因为我不能像列表一样轻松地与队列进行模式匹配？

Answer 1

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第一个元素。

Answer 2

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) 的整体复杂性。

BFS 糟糕的复杂性

BFS bad complexity

time-complexity

ocaml

breadth-first-search