Depth First Search

Here is simple code for depth 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) :- depthfirst([], Start, Solution). % depthfirst(+Path, +Node, -Solution). % Path is the path to Node from start. % % Node is it. depthfirst(Path, Node, [Node|Path]) :- goal(Node). % you have to write goal(+Node). depthfirst(Path, Node, Solution) :- successor(Node, Node1), % go to a new node \+ member(Node1, Path), % but don't go backwards! depthfirst([Node|Path], Node1, Solution).

For more details on (\+)/2. This is a form of " not ". It must be used with care.

Jonathan Hodgson
Last Changed: 1999/10/07