深度优先搜索：不变性和速度是互斥的吗？

Question

我在学校学到的 DFS 是这样的：

(* graph representation: ith element of the array is a list of successors of the node i *)
let graph_example = [|
  [1; 2];
  [3; 0; 2];
  [0; 1];
  [1]
|]

let dfs graph start_node =
  let visited = Array.make (Array.length graph_example) false in
  let rec dfs_rec node =
    if not visited.(node) then begin
      visited.(node) <- true;
      (* Do something with node *)
      Printf.printf "%d\n" node;
      List.iter dfs_rec graph.(node)
    end
  in
  dfs_rec start_node

示例图：

这个版本很好，因为它简单、实用，并且运行时间为 O(|E| + |V|)（即线性）（|E| 是边数，|V| 是顶点数）。

但是，它会改变

visited

数组。据我了解，这在 Ocaml 中有些反惯用，如果有办法的话应该避免这样做。那么有没有办法写一个不可变的版本呢？

我从这个问题看了一下Lhooq的DFS：https://stackoverflow.com/a/37738261 它是不可变的，并且它本质上（根据我的理解）用所有访问过的节点的列表字典替换了数组，并使用函数

List.mem

来检查节点是否已经被访问过。 问题是，

List.mem

似乎是线性时间（我在这里猜测，它没有写在文档中，所以我可能是错的），而数组访问是 O(1) 。所以总复杂度至少是 O(|E| + |V|^2) （即二次）时间，这是一个耻辱。

那么有没有办法改进这一点，或者你是否必须接受不可变版本会更慢？

Answer 1

首先，使用完全由函数拥有的局部可变变量在 OCaml 中是惯用的。应避免使用全局可变变量用于程序各个部分之间的远程通信。

其次，使用

List.mem

的代码并不惯用，因为

mem

是道德上属于

set

s 的函数。

因此，可变代码的直接翻译就是用一组访问过的节点替换访问过的数组：

module Node_set = Set.Make(Int)

let dfs graph start_node =
  let rec dfs_rec visited node =
    if Node_set.mem node visited then visited else
      let visited = Node_set.add node visited in
      List.fold_left dfs_rec visited graph.(node)
  in
  ignore (dfs_rec Node_set.empty start_node)

那么遍历的复杂度取决于集合实现中搜索的复杂度，对于标准实现来说最多是 O(ln V)。这个时间常数可以通过使用专门的数据结构来改进。然而，这种对数复杂度通常就足够了。毕竟，对于可以由算法的数组版本处理的图，

ln V

最多为 64，而集合版本可以适应任意大小的（稀疏和惰性）图。