使用纯功能深度优先搜索时如何防止循环

Question

我有一个图，它实现为连接任意节点的边列表，数据类型定义如下。

type edge = int * int;;
type graph = edge list;;

我将如何执行纯功能深度优先搜索同时避免陷入循环？我不太确定如何在保持纯功能的同时跟踪所有访问过的节点。答案可能是一些微不足道的东西，出于某种原因我在概念上没有掌握。

Answer 1

搜索功能有一个跟踪访问节点的参数。在 FP 中，其中一个见解是您可以不断地更深入地调用（使用尾调用）。因此，您可以通过所有调用传递参数，同时添加新节点。

另一个参数可以是您计划稍后访问的节点。对于 DFS，这将像堆栈一样工作。