我使用邻接列表来表示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进行模式匹配?
q @ graph的复杂性。(t)非常大,因为它是O(| q |)。所以我的复杂性非常糟糕,因为在每个步骤中我都会连接两个列表,这很重要。
你是绝对正确的 - 这是你的BFS的瓶颈。你应该很高兴能够使用Queue
模块,因为根据https://ocaml.org/learn/tutorials/comparison_of_standard_containers.html插入和获取元素的操作是O(1)。
OCaml中队列和列表之间的区别之一是队列是可变结构,因此您需要使用非纯函数,如add
,take
和top
,它们分别从前面插入元素,从前面弹出元素并返回第一个元素。
如果我没弄错的话,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)的整体复杂性。