ocaml图遍历：如何保存访问节点？

Question

我在试图用DFS遍历一个图。

但是，当我试图通过访问节点列表作为函数的参数，我发现有一个问题。

当我具备除了其前一个节点没有连接的节点，递归调用结束，有关访问节点消失，所以陷入无限循环的信息的节点达到...

是否有任何的方式来保持关于访问节点的信息，除了使用命令的方式？

Answer 1

详细阐述Jeffrey的答案，你有几种不同的风格可用。我在这里只给出了我没有测试过的片段，所以可能会有小的或大的错误。

1. 您可以在任何地方使用的副作用：

   module NodeSet = Set.Make(...) 
   
   let traverse action graph_root = 
       let visited = ref NodeSet.empty in 
       let rec loop node = 
       action node; 
       visited := NodeSet.add node !visited; 
       let handle child = 
        if not (NodeSet.mem child !visited) 
        then loop acc child in 
       List.iter handle (children node) 
       in loop graph_root 
   

   的“拜访”势在必行功能action适用于 图中的所有节点。

2. 可以遍历的状态存储在一个可变的引用被访问的节点，但是螺纹 作为直接的累加器acc代替 测序副作用。这将对应于国家monad的使用 。

   let traverse action init_state graph_root = 
       let visited = ref NodeSet.empty in 
       let rec loop acc node = 
       let acc = action acc node in 
       visited := NodeSet.add node !visited; 
       let handle acc child = 
        if NodeSet.mem child !visited 
        then acc 
        else loop acc child in 
       List.fold_left handle acc (children node) 
       in loop init_state graph_root 
   

3. 您可以重复这种状态下，通过逻辑还通过走访 节点的信息。

   let traverse action init_state graph_root = 
       let rec loop acc visited node = 
       let acc = action acc node in 
       let visited = NodeSet.add node visited in 
       let handle (acc, visited) child = 
        if NodeSet.mem child !visited 
        then (acc, visited) 
        else loop acc visited child in 
       List.fold_left handle (acc, visited) (children node) 
       in loop init_state NodeSet.empty graph_root 
   

4. 最后，你可以通过 有关哪些节点应该在第一 递归调用计算旁边移动到尾递归遍历。这对应于继续传递样式的一般转换，但是具有继续的域特定表示 （仅仅是要访问的节点）。

   let traverse action init_state graph_root = 
       let rec loop acc visited = function 
       | [] -> acc 
       | node::to_visit -> 
        if NodeSet.mem node visited then loop acc visited to_visit 
        else begin 
        let acc = action acc node in 
        let visited = NodeSet.add node visited in 
        let to_visit = children node @ to_visit in 
        loop acc visited to_visit 
        end 
       in loop NodeSet.empty init_state [graph_root] 
   

   杰弗里的言论，与此演示文稿，可以在 遍历顺序从DFS通过简单地改变着to_visit 更新更改为BFS，添加子节点的序列的末端，而 比年初（这需要在算法上有效的队列结构为 ）。

Answer 2

看看这个的一种方法是，你想要转发来尝试图中其他可能的节点，而不是返回（就像你会这样做，例如遍历一棵树）。您可以使用参数来描述您访问过的节点，但您计划访问的节点。访问参数最初只是第一个节点。每次到达新节点时，都会将所有未访问的相邻节点（通过查看访问节点集可以看出）添加到未访问节点集，并以递归方式继续。然后，DFS和BFS之间的区别就在于您对要访问的节点列表进行排序。

在函数式编程中，有许多次不是从函数返回时，而是调用函数来做下一件事。 （这就是为什么尾递归有时很重要。）