Breadth First

Transitive Closures and Prolog are nearly synonymous. However, there are times we want to do GraphTraversal by listifying the tree, for instance with Puzzle Solving 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:

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

1. Top Down Recursion
2. Bottom Up Recursion

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 History Filtering.