有没有办法将基于矩阵的图形表示转换为 OCaml 中的邻接表之类的东西？

Question

通常，在编程面试中，您会遇到一个问题，要求您使用 DFS 或 BFS 之类的方法遍历图形的二维矩阵表示 problem on LeetCode。不幸的是，在遇到节点补丁时循环元素和运行 dfs 的典型算法很难在功能上实现。我想知道是否有一种简单的方法可以将 2D 矩阵转换为 OCaml 中的邻接表表示，以便函数算法可以获得更有效的解决方案。

Answer 1

我猜你会喜欢这样的东西：

let to_adjacency_list m =
  (* Create an array of the size of the matrix with empty lists as values *)
  let ml = Array.init (Array.length m) (fun _ -> []) in
  (* For each cell (i, j) that contains true, append j to the list at index i *)
  Array.iteri
    (fun i a -> Array.iteri (fun j v -> if v then ml.(i) <- j :: ml.(i)) a)
    m;
  (* Reverse all the created lists for readability and convert the array to a list *)
  Array.to_list (Array.map List.rev ml)

如果我将它应用于矩阵：

# let m =
  [|
    [| true; true; true; true; false |];
    [| true; true; false; true; false |];
    [| true; true; false; false; false |];
    [| false; false; false; false; false |];
  |] in to_adjacency_list m;;

- : int list list = [[0; 1; 2; 3]; [0; 1; 3]; [0; 1]; []]

Answer 2

Unfortunately, the typical algorithms of looping over the elements and running a dfs when you encounter a patch of nodes are hard to implement functionally.

相反，它们实施起来非常容易和自然。让我们展示一下。 LeetCode 的输入表示为，


grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

直接映射到 OCaml 为

let grid = [
  ["1";"1";"1";"1";"0"];
  ["1";"1";"0";"1";"0"];
  ["1";"1";"0";"0";"0"];
  ["0";"0";"0";"0";"0"]
]

唯一的语法差异是您必须使用 ; 而不是 , 作为分隔符。

OCaml 中的迭代，以及一般的函数式语言，都是使用迭代器表示的。迭代器是一个高阶函数，它接受一个容器和另一个函数，并将该函数应用于该容器的每个元素。因此不需要用于迭代的特殊语言结构，如 for 或 while¹.

迭代器大致可以分为两组：文件夹和映射器。文件夹对每个元素应用一个函数并累积结果。映射器创建一个新的数据结构，其中每个元素都是原始元素的映射（转换）。不映射每个元素的映射器，即生成可能小于输入的输出数据结构的映射器，称为 过滤器。最后，每个映射器都可以（通常是）使用文件夹实现，因此文件夹是最通用的迭代形式。

现在，当我们掌握了这些知识后，我们可以看看 List to see what iterators it provides. Since we need to find the number of isolated islands, the input representation is not optimal and we will need to transform it into something more suitable. From the graph theory perspective, an island is a connected component，我们需要将我们的土地划分为一组岛屿。显然，我们的输入数据结构不是很合适，因为它不允许我们有效地查询一个元素是否连接到其他元素。单个 linked 列表中的所有查询都是线性的，因为它们必须从第一个元素到最后一个元素。所以我们需要找到一个更好的数据结构来表示我们关于世界地理的信息。

因为我们只对 is_land 感兴趣，所以有效的表示是一组位置，其中每个位置都表示为 x 和 y 坐标，

type pos = {x : int; y : int}

让我们为职位类型定义一个模块，并在其中添加一些有用的功能，

module Pos = struct
  type t = pos
  let compare = compare   (* use structural compare *)
  let zero = {x=0; y=0}
  let north p = {p with y = p.y - 1}
  let south p = {p with y = p.y + 1}
  let east p = {p with x = p.x + 1}
  let west p = {p with x = p.x - 1}
end

最后，我们准备好将世界定义为一组位置，

module World = Set.Make(Pos)

现在我们可以迭代我们的矩阵并创建一个世界，

let is_land = function "1" -> true | _ -> false

let make_world input : World.t =
  snd @@
  List.fold_left (fun (pos,map) ->
      List.fold_left (fun ({x;y},map) piece ->
          if is_land piece
          then ({x=x+1; y}, World.add {x;y} map)
          else ({x=x+1; y}, map))
        ({x=1; y = pos.y + 1},map))
    ({Pos.zero with x = 1},World.empty)
    input

了解我们如何使用列表迭代器对矩阵执行迭代。

接下来，我们将实施union-find algorithm to partition a world into a set of islands. Let's develop it topdown. The union-find algorithm partitions a set of elements into a set of non-intersecting sets (colloquially called quotient set)。我们的初始集合是 World.t ，即所有位置为陆地的集合。对于每个位置，我们需要找到该位置 is_connected 所在的岛屿列表。我们现在需要精确定义 is_connected 的含义。就我们世界的几何学而言，位于 pos 位置的一块土地与一个岛屿 island 相连，如果它属于 island 或者它的任何邻居属于 island，其中 pos 中的 neighbors 是

let neighbors pos = [
  Pos.north pos;
  Pos.south pos;
  Pos.east pos;
  Pos.west pos;
]

所以 is_connected 是使用 List.exists 迭代器定义的，

let is_connected pos island =
  List.exists (fun x -> World.mem x island)
    (pos :: neighbors pos)

现在，我们可以编写一个函数，将商集的岛屿划分为一块土地所属的岛屿集和不与该块土地相连的岛屿集。使用List.partition迭代器很容易实现，

let find_islands pos =
  List.partition (is_connected pos)

如果一个元素属于几个岛屿，那么就意味着它是一个连接元素，一个link，它连接了几个在我们发现这个元素之前被认为是断开的岛屿。我们需要一个函数，将一个岛的几个部分连接成一个岛。同样，我们可以使用 List.fold_left，

let union = List.fold_left World.union World.empty

现在，我们拥有了所有必要的构建元素来找到我们的主要算法，

let islands world =
  World.fold (fun pos islands ->
      let found,islands = find_islands pos islands in
      World.add pos (union found) :: islands)
    world []

让我们重申一下它的实现。对于我们世界的每一部分，我们将我们的初始岛屿集（从一个空集开始）划分为该部分属于的岛屿和不属于的岛屿。然后我们 union 找到的岛屿，并将当前棋子添加到新形成的岛屿中，并将该岛屿添加到岛屿集合中。

注意，在函数式编程语言中实现 union-find 是多么简单！

岛屿的数量显然是我们分区的基数，例如

let number_of_islands world = List.length (islands world)

最后，solve 函数，它采用指定形式的输入，returns 岛屿的数量定义为，

let solve input = number_of_islands (make_world input)

我们来玩一下，

# solve [
  ["1";"1";"1";"0";"0"];
  ["1";"1";"0";"1";"0"];
  ["1";"1";"0";"0";"0"];
  ["0";"0";"0";"0";"1"]
];;
          - : int = 3
# solve [
  ["1";"1";"1";"1";"0"];
  ["1";"1";"0";"1";"0"];
  ["1";"1";"0";"0";"0"];
  ["0";"0";"0";"0";"1"]
];;
          - : int = 2
# solve [
  ["1";"1";"1";"1";"0"];
  ["1";"1";"0";"1";"1"];
  ["1";"1";"0";"0";"1"];
  ["0";"0";"0";"0";"1"]
];;
          - : int = 1
#

看起来不错！但是，如果它从一开始就不起作用怎么办？我们需要调试它。在函数式编程中，调试很容易，因为您可以独立调试每个小函数。但是为此你需要能够打印你的数据，而我们的 World.t 是一种抽象数据类型，它被打印为 <abstr>。为了能够打印它，我们需要定义一些打印机，例如

let pp_pos ppf {x; y} = Format.fprintf ppf "(%d,%d)" x y
let pp_comma ppf () = Format.fprintf ppf ", "
let pp_positions ppf world =
  Format.pp_print_list ~pp_sep:pp_comma pp_pos ppf
    (World.elements world)
let pp_world ppf world =
  Format.fprintf ppf "{%a}" pp_positions world

现在我们可以安装它了（我假设你是运行这个使用 ocaml 或 utop 解释器的程序），现在我们可以看到我们的算法如何划分我们的世界变成岛屿，

# #install_printer pp_world;;

# islands @@ make_world [
  ["1";"1";"1";"0";"0"];
  ["1";"1";"0";"1";"0"];
  ["1";"1";"0";"0";"0"];
  ["0";"0";"0";"0";"1"]
];;
          - : World.t list =
[{(5,4)}; {(4,2)}; {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1)}]

¹⁾ 我们在 OCaml 中仍然有它们，但很少使用。

有没有办法将基于矩阵的图形表示转换为 OCaml 中的邻接表之类的东西？

Is there a way to convert a matrix based graph representation into something like an adjacency list in OCaml?

ocaml

functional-programming