Search code examples
algorithmgraphocamldepth-first-searchpurely-functional

How to prevent cycles when using a purely functional depth-first search

I have a graph that is implemented as a list of edges connecting arbitrary nodes, with the data types defined below.

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

How would I perform a purely functional depth-first search while avoiding getting stuck on a cycle? I am not quite sure of how to keep track of all the nodes visited while remaining purely functional. The answer is probably something trivial that I am not conceptually grasping for some reason.

Solution

  • The search function has a parameter that tracks visited nodes. In FP one of the insights is that you can keep calling deeper and deeper (with tail calls). So you can pass the parameter along through all the calls, adding new nodes as you go.

    Another parameter could be the nodes you plan to visit later. For DFS this would work like a stack.