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.

DifferenceLists are a more efficient way of appending to the back of long lists in SWI Prolog. But in these simple examples, I'm simply switching the order of append(?List1, ?List2, ?List1AndList2).

Initially, lets assume no cycles as in the first example:

tree.svg

There are two basic ways of doing list recursion in Prolog:

  1. TopDownRecursion

  2. BottomUpRecursion

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.

tree_cycle.svg

A way to use a history list to filter out visited nodes is shown in HistoryFiltering.

BreadthDepthFirst (last edited 2021-09-06 20:09:09 by RobertLaing)