OCAML深度优先搜索

我一直在做一个OCaml的教程（不要问我为什么，我只是决定扩大我的语言知识，我猜），我已经到了我所处的位置与图表一起工作。该教程教会了我如何在图形上进行广度优先搜索，这可以很好地实现。然而，我一直在努力寻找深度优先搜索的算法，这是本教程的其中一个方面，“我们建议您使用深度优先方法来尝试，但我们不会告诉您如何做吧。“OCAML深度优先搜索

我试图执行它像这样：let rec dfs graph start end。也就是说，我一直试图在边界列表（），起始节点（start）和结束节点（end）中进行。

我用边的列表中创建我的图...

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

不过，我完全失去了到哪里何去何从。有关如何让我走的任何建议？谢谢。

来源

2016-04-29 jpabene

通常的一句话总结是，深度优先搜索与广度优先搜索相同，只不过您用堆栈替换未访问节点的队列。您可以尝试以这种方式修改您的广度优先搜索实现。 –

用于列出节点后继的函数可能会让您更容易。 – PatJ

所以，我做到了，但我觉得很奇怪，如果您必须在其中搜索，则将图表表示为列表。地图会好很多。总之，这里的它是如何做：

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 ...
  
  （事做这个所谓的演算和一些奇怪的事情规则称为ETA转换其中指出：
  
  λ x · ux η u (x ∉ fv(u))（fv(u)是U的自由变量）:-P）（这是什么意思，如果在OCaml中，如果你写fun x -> f x你可以有写f相反，它是完全等同。）
- 回到其所有访问节点都被添加的访问节点列表

^h我帮助过。

来源

2016-06-10 00:35:05 Lhooq

OCAML深度优先搜索

回答

相关问题