OCAML Depth-First Search

Question

我一直在OCaml做一个教程(不要问我为什么,我只是决定扩展我的语言知识,我猜)我已经到了我正在处理图形的地步.该教程教我如何在图表上进行广度优先搜索,我可以很好地实现.然而,我一直在努力使用深度优先搜索的算法,这是教程中的一个,"我们建议您尝试使用深度优先方法,但我们不会告诉您如何做吧."

我正试图这样实现它:let rec dfs graph start end.也就是说,我一直试图在我接受edge(graph)列表,起始节点(start)和结束节点(end)的位置.

我使用边缘列表创建了我的图形...

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

但是,我完全不知道从哪里开始.关于如何让我去的任何建议？谢谢.

Answer 1

所以，我这样做了，但我觉得很奇怪，如果你必须在图表中进行搜索，那么你将图表表示为列表。有地图就更好了。无论如何，这是如何完成的：

\n

let edges = [\n  ("a", "b"); ("a", "c");\n  ("a", "d"); ("b", "e");\n  ("c", "f"); ("d", "e");\n  ("e", "f"); ("e", "g")\n];;\n\nlet successors n e = \n  List.map (fun (_, v) -> v) (List.filter (fun (u, _) -> n = u) e)\n\nlet dfs graph start f =\n  let rec rdfs visited node =\n    if not (List.mem node visited) then\n      begin\n        f node;\n        let s = successors node graph in\n        List.fold_left rdfs (node::visited) s\n      end\n    else visited\n  in rdfs [] start\n\n let () = let _ = dfs edges "a" print_string in ()\n

\n

首先，定义一个successors函数，它将为您提供节点的每个直接后继（该List.filter部分为您提供边缘，该List.map部分将结果边缘分为两部分，并仅保留第二部分（第一个自然是您要为其创建的节点）正在寻找接班人）。

\n

该dfs函数定义了一个内部函数，该函数执行两件事：检查我们正在处理的节点是否已被访问。

\n

\n

• 如果是，没有任何变化，我们只返回相同的访问节点列表（可能还有其他一些事情，具体取决于您想要对搜索执行的操作）。

  \n
\n

• 如果没有，那么

  \n
\n

• 我们将赋予的函数应用于dfs当前节点，

  \n
\n

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

  \n
\n

• 我们带他的继任者，

  \n
\n

• 我们将这个函数应用于每一个，（这里有一个小技巧，因为我们有

  \n

  List.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

  \n

  和

  \n

  rdfs : string list -> string -> string list

  \n

  而不是写作

  \n

  List.fold_left (fun visited node -> rdfs visited node) ...

  \n

  我们可以写

  \n

  List.fold_left rdfs ...

  \n

  （与名为 Lambda 演算的奇怪事物和一些名为eta 转换的规则有关，该规则指出：

  \n

  \xce\xbb x \xc2\xb7 ux \xce\xb7 u (x \xe2\x88\x89 fv(u))（fv(u)作为 u 的自由变量）：-p）（这意味着在 OCaml 中，如果你写fun x -> f x你可以写f，它是严格等价的。）

  \n
\n

• 我们返回已访问节点列表，其中已添加所有已访问节点

  \n
\n

\n

希望我有所帮助。

\n