OCAML 深度优先搜索

Question

我一直在做 OCaml 的教程(不要问我为什么，我只是决定扩展我的语言知识，我猜)并且我已经到了使用图表的地步。该教程教我如何在图形上进行广度优先搜索，我可以很好地实现。但是，我一直在为深度优先搜索的算法苦苦挣扎，这是本教程中的内容之一，“我们建议您尝试使用深度优先方法，但我们不会告诉您如何做吧。”

我正在尝试像这样实现它:let rec dfs graph start end .也就是说，我一直在尝试使用边列表( graph )、起始节点( start )和结束节点( end )来做这件事。

我已经使用边列表创建了我的图表......

let edges = [
  ("a", "b"); ("a", "c");
  ("a", "d"); ("b", "e");
  ("c", "f"); ("d", "e");
  ("e", "f"); ("e", "g")
];;

但是，我完全不知道从哪里开始。关于如何让我前进的任何建议？谢谢。

Answer 1

所以，我做到了，但我觉得奇怪的是，如果您必须在其中进行搜索，您将图表表示为列表。有 map 会好很多。无论如何，这是如何完成的:

let edges = [
  ("a", "b"); ("a", "c");
  ("a", "d"); ("b", "e");
  ("c", "f"); ("d", "e");
  ("e", "f"); ("e", "g")
];;

let successors n e = 
  List.map (fun (_, v) -> v) (List.filter (fun (u, _) -> n = u) e)

let dfs graph start f =
  let rec rdfs visited node =
    if not (List.mem node visited) then
      begin
        f node;
        let s = successors node graph in
        List.fold_left rdfs (node::visited) s
      end
    else visited
  in rdfs [] start

 let () = let _ = dfs edges "a" print_string in ()

首先，定义一个 successors将为您提供节点的每个直接后继的函数( List.filter 部分为您提供边， List.map 部分将结果边分成两部分并仅保留第二部分(第一个自然是节点您正在寻找继任者)。 dfs function 定义了一个内部函数，它做两件事，检查我们正在处理的节点是否已经被访问过。

如果是，没有任何变化，我们只返回相同的访问节点列表(可能还有其他一些事情，取决于您想对搜索做什么)。

如果没有，那么

我们将我们给的函数应用到 dfs到当前节点，

我们将此节点添加到访问过的节点中，

我们把他的继任者，

我们将函数应用于每个函数，(这里有一个小技巧，因为我们有List.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a和rdfs : string list -> string -> string list而不是写作List.fold_left (fun visited node -> rdfs visited node) ...我们可以写List.fold_left rdfs ...(这与 Lambda 微积分这个奇怪的东西和一些称为 eta 转换的规则有关，它指出:λ x · ux η u (x ∉ fv(u)) ( fv(u) 是 u 的自由变量) :-p) (这意味着在 OCaml 中，如果你写 fun x -> f x 你可以写成 f，它是严格等价的。)

我们返回已添加所有访问节点的访问节点列表

希望我有所帮助。