深度优先搜索（DFS）：不可变性与执行速度是否互斥？

我在学校学到的DFS实现如下（图的表示：数组第i个元素是节点i的后继节点列表）：

(* 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的惯用风格更倾向于避免可变状态，所以我想知道是否存在不可变的DFS实现方式？

我参考过一种不可变的DFS实现，它用存储已访问节点的列表来替代数组，通过List.mem判断节点是否已访问。但问题在于List.mem的时间复杂度是线性的，而数组访问是O(1)，所以这种实现的总时间复杂度至少是O(|E| + |V|²)（二次时间），这显然不够高效。

那么有没有办法优化这种不可变实现，还是说必须接受不可变版本的速度更慢？

解答 #

要在OCaml中实现高效的不可变DFS，核心是找到一种不可变且支持O(1)或近似O(1)访问的已访问集合，替代线性时间的List.mem。以下是几种可行的优化方向：

1. 使用不可变哈希集合

借助第三方库（如Core的不可变Hash_set、containers库的CCHashSet）提供的不可变哈希集合，这类结构的成员查询平均时间复杂度为O(1)，能将整体时间复杂度拉回到线性级别。

示例实现：

open Core

let dfs_immutable graph start_node =
  let rec dfs_rec node visited =
    if not (Hash_set.mem visited node) then
      let new_visited = Hash_set.add visited node in
      Printf.printf "%d\n" node;
      List.fold_left (fun acc n -> dfs_rec n acc) new_visited graph.(node)
    else
      visited
  in
  ignore (dfs_rec start_node (Hash_set.empty (module Int)))

2. 使用不可变位集

如果节点是连续的整数（从0开始编号），可以用不可变位集存储已访问状态。位集的查询和更新都是O(1)（按位操作），效率极高。小规模节点场景下，甚至可以用整数类型（如int64）手动实现位集。

示例思路（适用于节点数≤系统整数位宽）：

let dfs_bits graph start_node =
  let rec dfs_rec node visited_bits =
    let mask = 1 lsl node in
    if (visited_bits land mask) = 0 then
      let new_bits = visited_bits lor mask in
      Printf.printf "%d\n" node;
      List.fold_left (fun acc n -> dfs_rec n acc) new_bits graph.(node)
    else
      visited_bits
  in
  ignore (dfs_rec start_node 0)

3. 使用标准库不可变集合

OCaml标准库通过Set.Make生成的不可变平衡二叉搜索树，成员查询和插入的时间复杂度为O(log|V|)，整体时间复杂度变为O((|E|+|V|)log|V|)，远优于二次时间，且无需依赖第三方库。

示例实现：

module IntSet = Set.Make(Int)

let dfs_set graph start_node =
  let rec dfs_rec node visited =
    if not (IntSet.mem node visited) then
      let new_visited = IntSet.add node visited in
      Printf.printf "%d\n" node;
      List.fold_left (fun acc n -> dfs_rec n acc) new_visited graph.(node)
    else
      visited
  in
  ignore (dfs_rec start_node IntSet.empty)

总结 #

不需要接受不可变版本一定更慢：

• 借助第三方库的不可变哈希集合，能达到和可变数组接近的线性时间效率；
• 节点编号连续时，位集是最优选择；
• 仅用标准库的话，平衡BST集合能将时间复杂度控制在O((|E|+|V|)log|V|)，足够应对多数场景。

另外，OCaml并非完全排斥可变状态——如果性能是首要需求且场景简单，原来的可变数组版本也是合理选择，惯用风格只是建议而非绝对规则。

内容的提问来源于stack exchange，提问作者Dr_McFish