Breadth First Search

Here is simple code for breadth first search. It is taken from the book of Ivan Bratko. % solve(+Start,-Solution) % Solution is an acyclic path (in reverse order) % from Start to a goal % solve(Start, Solution) :- breadthfirst( [[Start]], Solution). % breadthfirst(+[Paths], -Solution). % Paths is the list of paths being explored % % Node is it. breadthfirst([ [Node|Path]| _OtherPaths], [Node|Path]) :- goal(Node). % you have to write goal(+Node). breadthfirst([Path |Paths], Solution) :- extend(Path, NewPaths), append(Paths, newpaths, Paths1), breadthfirst(Pths1, Solution). extend([Node|Path], NewPaths) :- bagof( [NewNode, Node, |Path], (successor(Node, NewNode), not member(NewNode, [Node|Path])), NewPaths), !. extend(Path, []).
  1. For more details on (\+)/2. This is a form of " not ". It must be used with care.
  2. For details on the cut (!/0)
  3. For details on bagof/3. Note in particular that bagof fails when the goal has no solutions. On the other hand findall/3 does not.

Jonathan Hodgson
Last Changed: 1999/10/07