Depth and Breadth First searches
TransitiveClosures and Prolog are nearly synonymous. However, there are times we want to do GraphTraversal by listifying the tree, for instance with PuzzleSolving where we don't initially have a tree to search via a transitive closure. This involves storing unexplored nodes in a list, conventionally called the frontier. Whether children of the currently visited node are stacked at the front (depth first) or queued to the back (breadth first) of the frontier can make a huge difference to the speed and quality of search results.
Initially, lets assume no cycles as in the first example:
There are two basic ways of doing list recursion in Prolog:
Avoiding cycle traps
Here node k has been turned into a double cycle trap with the addition of arc(k, e) and back to itself with arc(k, k). The above code will go into an infinite loop without modification.
A way to use a history list to filter out visited nodes is shown in HistoryFiltering.