ocaml - ocaml 图遍历：如何保留访问的节点？

Question

我正在尝试使用 DFS 遍历图表。

但是当我尝试将访问的节点列表作为函数的参数传递时，我发现有问题。

当我到达除前一个节点外没有连接节点的节点时，递归调用结束，访问节点的信息消失，因此陷入无限循环......

除了使用命令式方式之外，还有什么方法可以保留有关已访问节点的信息？

score 4 · Accepted Answer

详细说明 Jeffrey 的回答，您可以使用几种不同的样式。我在这里只给出我没有测试过的片段，所以可能会有小错误或大错误。

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

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图中的所有节点。

您可以将访问的节点存储在可变引用中，但是将遍历的状态作为累加器线程化，acc而不是直接对副作用进行排序。这将对应于使用 State 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

您可以重用此状态传递逻辑来传递访问节点信息。

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

最后，您可以通过传递有关在第一次递归调用中接下来应该计算哪些节点的信息来移动到尾递归遍历。这对应于向延续传递样式的一般转换，但具有特定于域的延续表示（只需访问节点）。
```
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]
```
Jeffrey 评论说，通过本演示文稿，您可以通过简单地更改to_visit 更新方式将遍历顺序从 DFS 更改为 BFS，将子节点添加到序列的末尾而不是开头（这需要队列结构在算法上是有效的） .

score 2 · Accepted Answer

看待这一点的一种方法是，您希望继续尝试图中的其他可能节点，而不是返回（例如，遍历树）。您可以拥有不仅描述您访问过的节点，还描述您计划访问的节点的参数。to-visit 参数最初只是第一个节点。每次到达新节点时，您都将任何未访问的相邻节点（您可以通过查看已访问的节点集来判断）添加到未访问的节点集，并以这种方式递归地继续。那么，DFS 和 BFS 之间的区别在于您对要访问的节点列表进行排序的方式。

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

ocaml - ocaml 图遍历：如何保留访问的节点？

2 回答 2

Related

Reference