一般来说，在编程面试中，你会得到一个问题，要求你使用DFS或BFS之类的东西遍历图的2D矩阵表示，就像LeetCode上的这个问题一样。不幸的是，在遇到节点补丁时循环元素和运行 dfs 的典型算法很难在功能上实现。我想知道是否有一种简单的方法可以将 2D 矩阵转换为 OCaml 中的邻接列表表示形式，以便函数算法可以获得更有效的解决方案。
不幸的是，在遇到节点补丁时循环元素并运行 dfs 的典型算法很难在功能上实现。
相反，它们很容易和自然地实施。让我们展示一下。 来自 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或while1。
迭代器可以大致分为两组：文件夹和映射器。文件夹对每个元素应用一个函数并累积结果。映射器创建一个新的数据结构，其中每个元素都是原始元素的映射(转换)。不映射每个元素的映射器，即生成可能小于输入的输出数据结构的映射器，称为过滤器。最后，每个映射器都可以(并且通常)使用文件夹实现，因此文件夹是最通用的迭代形式。
现在，当我们掌握了这些知识时，我们可以查看列表以查看它提供了哪些迭代器。由于我们需要找到孤岛的数量，因此输入表示不是最佳的，我们需要将其转换为更合适的内容。从图论的角度来看，岛屿是一个相连的组成部分，我们需要将我们的土地划分为一组岛屿。显然，我们的输入数据结构不是很合适，因为它不允许我们有效地查询一个元素是否连接到其他元素。单链表中的所有查询都是线性的，因为它们必须从第一个元素到最后一个元素。因此，我们需要找到一个更好的数据结构来表示我们关于世界地理的信息。
由于我们只对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
了解我们如何使用 List 迭代器对矩阵执行迭代。
接下来，我们将实现联合查找算法，将一个世界划分为一组岛屿。让我们自上而下地开发它。联合查找算法将一组元素划分为一组非相交集(俗称商集)。我们的初始集合是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)
如果一个元素属于几个岛，那么这意味着它是一个连接元素，一个链接，连接几个在我们找到这个元素之前被认为是断开连接的岛。我们需要一个函数，将一个岛的几个部分连接成一个岛。同样，我们可以为此使用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找到的岛屿，并将当前部分添加到新形成的岛屿中，并将该岛屿添加到岛屿集中。
请注意，在函数式编程语言中实现联合查找是多么简单！
岛屿的数量显然是我们分区的基数，例如，
let number_of_islands world = List.length (islands world)
最后，solve函数以指定的形式接受输入并返回岛的数量，定义为：
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)}]
1)我们在OCaml中仍然有它们，但很少使用。
我想你会喜欢这样的东西：
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]; []]