OCAML Depth-First Search-Java 学习之路

我一直在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")
];;

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

1 回答

2
所以，我做到了，但我觉得很奇怪，如果你必须在其中搜索，你将图表表示为列表 . 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 函数定义了一个内部函数，它执行两项操作，检查我们正在处理的节点是否已被访问过 .
- 如果是，没有任何变化，我们只返回相同的访问节点列表（也许还有其他一些东西，具体取决于你想要对你的搜索做什么） .
- 如果不是，那么
- 我们将我们给 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) 是你的自由变量）:- p）（如果你在OCaml中这意味着什么，如果你写 fun x -> f x 你可以写 f ，它是严格等同的 . ）
- 我们返回已访问的节点列表，其中添加了所有访问过的节点
希望我帮忙 .
回复于 2024-05-03T20:08:28+08:00

OCAML Depth-First Search

1 回答

相关问题