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

Question

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

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

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

Answer 1

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

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