Breadth and Depth First Searches with a History list to avoid cycles

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 code in TopDownRecursion and BottomUpRecursion will go into an infinite loop without modification.

tree_cycle.svg

One way to fix this is to remember which nodes have already been visited, and not visit them a second time. In the above example, we're already keeping what's generally called a history list which can be used with member(?Elem, ?List), or alternatively memberchk(?Elem, +List) which returns true the first time it finds an element, so may be slightly more efficient in this case.

getchildren has been modified to filter out children already in the history list.

arc(a, b).
arc(a, c).
arc(a, d).
arc(b, e).
arc(b, f).
arc(c, g).
arc(c, h).
arc(c, i).
arc(d, j).
arc(e, k).
arc(f, l).
arc(f, m).
arc(h, n).
arc(i, o).
arc(i, p).
arc(j, q).
arc(j, r).
arc(j, s).
arc(k, e).
arc(k, k).
arc(m, t).

getchildren(Parent, History, Children) :-
    findall(Child, (arc(Parent, Child), \+memberchk(Child, History)), Unsorted),
    sort(Unsorted, Children).

depthfirst([Start], Path) :-
    depthfirst_([Start], [], RevPath),
    reverse(RevPath, Path).

depthfirst_([], Acc, Acc).

depthfirst_([Node|Frontier], Visited, Acc) :-
    getchildren(Node, [Node|Visited], Children),
    append(Children, Frontier, NewFrontier),
    depthfirst_(NewFrontier, [Node|Visited], Acc).

breadthfirst([Start], Path) :-
    breadthfirst_([Start], [], RevPath),
    reverse(RevPath, Path).

breadthfirst_([], Acc, Acc).

breadthfirst_([Node|Frontier], Visited, Acc) :-
    getchildren(Node, [Node|Visited], Children),
    append(Frontier, Children, NewFrontier),
    breadthfirst_(NewFrontier, [Node|Visited], Acc).

Again as in the acyclical examples in TopDownRecursion and BottomUpRecursion, breadthfirst([a], Path) will return the nodes in alphabetical order whereas depthfirst([a], Path) returns Path = [a, b, e, k, f, l, m, t, c, g, h, n, i, o, p, d, j, q, r, s]

This approach is taken further in IterativeDeepening, where depth first search mimics breadth first by increasing the depth limit a step at a time. The visited nodes produced by one call to depthfirst are then used as the starting frontier of the next. In PrunedIterativeDeepening, this recursive process is used to prune unwanted branches of the search space while growing towards the desired goal.

HistoryFiltering (last edited 2021-09-12 21:13:57 by RobertLaing)