使用 Union-Find 得到等价物类

Question

我有一个简单的union-find代码如下：

let rec find p x =
      if p.(x) = x
      then x
      else
        let y = find p (p.(x)) in
        p.(x) <- y;
        y;;       
let union x y p =
  p.(find p y) <- p.(find p x);
  p

示例：

let a = [|0;1;2;3;4|]

let print_array a =
 Array.iter (fun i -> Printf.printf "%i" i; print_string " ") a

let print_union =
  let a = union 0 1 a in
  print_string "Result union (0, 1): ";
  print_array a;
  print_string "\n"

结果将是：

Result union (0, 1): 0 0 2 3 4

我很难进一步获得不相交集。例如上面的例子我想得到：{0,1},{2},{3},{4}

感谢您的帮助。

Answer 1

由于显而易见的原因，如果不检查整个结构就无法打印该结果。

因此，您想从所有联合发现中收集居民：

let print_classes a =
 (* Let's first create an array for storing the classes *)
 let classes = Array.make (Array.length a) [] in

 (* Let's now populate it!
    I'm going backwards in the array to have nicer printing *)
 for i = (Array.length classes) - 1 downto 0
 do classes.(a.(i)) <- i :: (classes.(a.(i))) done;

 (* And now the printing *)
 Array.iter (function
   | [] -> ()
   | h::t -> Printf.printf "{%d%a}" h
             (fun c -> List.iter (fun x -> Printf.fprintf c ",%i" x)) t
   )
   classes

为了简洁起见，我使用了 Printf 函数，您可以找到他们的文档 here。

请注意，这可能会得到改进，因为它创建了一个可能被 "almost not" 填充的潜在大数组。根据您使用此功能的频率，您可能希望将等价 class 与 class 领导者一起存储（我不得不这样做一次，我使用 Set 和Map 来自标准库）。

使用 Union-Find 得到等价物类

Use Union-Find to get the equivalence classes

ocaml

使用 Union-Find 得到等价物 类

Use Union-Find to get the equivalence classes

ocaml

使用 Union-Find 得到等价物类