BFS糟糕的复杂性

Question

我使用邻接列表来表示OCaml中的图形。然后我从节点s开始在OCaml中进行了以下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工作，因为我不能像列表一样轻松地与Queue进行模式匹配？

Answer 1

q @ graph的复杂性。（t）非常大，因为它是O（| q |）。所以我的复杂性非常糟糕，因为在每个步骤中我都会连接两个列表，这很重要。

你是绝对正确的 - 这是你的BFS的瓶颈。你应该很高兴能够使用Queue模块，因为根据https://ocaml.org/learn/tutorials/comparison_of_standard_containers.html插入和获取元素的操作是O（1）。

OCaml中队列和列表之间的区别之一是队列是可变结构，因此您需要使用非纯函数，如add，take和top，它们分别从前面插入元素，从前面弹出元素并返回第一个元素。

Answer 2

如果我没弄错的话，q @ graph。（t）的复杂性非常大，因为它是O（| q |）。

这确实是问题所在。你应该使用的是graph.(t) @ q。其复杂性为O（| graph。（t）|）。

你可能会问：这有什么不同？

区别在于| q |可以是从0到V * E的任何东西。图。（t）另一方面你可以使用。您最多访问一次图中的每个顶点一次，因此整体上会有复杂性

  O(\Sum_V |grahp.(v))

图中每个顶点的所有边的总和。换句话说：E。

这将带您了解O（V + E）的整体复杂性。