# How to avoid loop in a dept-search in a graph?

I must implement , in Lisp , a depth-search algorithm in an implict graph (namely a graph where I have the starting node, the goal node, and the successor function ,f, that give a node create his successors). There is a depth limit d. The algorithm must return a path (obviously cannot be minimal).

My problem is how manage the loop .

My first question is: If I use this following stupid method work it?

I have 2 list. The first is a LIFO ((I call it list1) when I insert in the head the succesor nodes. Evry time I expand the node in the head.

In the second list (I call it list2) I keep a list where put all nodes already met and every time that I expand a node I check if successor nodes obtained are in the list above (list2). For the nodes that are in it (in list2) I don't insert in list1.

This method sucks because in the worst case i must keep in list2 all nodes of the graph and I must search at every expansion if some successor nodes are in the list2. (for example, this method certainly works with breadth-first search) But at least it works? Or I would risk to cut relevant paths ?

Second question is: How can I implement it efficiently (pseudocode, or simply idea)?

Thanks in advance

• You want a Set rather than a List for the visited nodes. Common set representations are Red–Black Trees or Hash Tables. – amon Jul 8 '15 at 13:33

## 1 Answer

Use recursion:

``````;; you might want to implement sets using hash tables
(defun make-set (&rest elements)
elements)
(defun set-empty-p (s)
(null s))
(defun set-union (s1 s2)
(union s1 s2))
(defun depth-search (start end next max-depth
&key (seen (make-set start))
(depth 0) (path (list start)))
;; untested!
(when (eq start end)
(return path))
(when (= depth max-depth)
(return t))                 ; no path
(let ((candidates (set-difference (funcall next start) seen)))
(loop for candidate in candidates
for path = (depth-search candidate end next max-depth
:seen (set-union seen (make-set candidate))
:depth (1+ depth) :path (cons candidate path))
do (when (listp path) (return path))
finally (return t))))
``````
• Thanks for the reply. But I believe that with this implementation are stored in "seen" all nodes already seen losing the advantage of depth-search: linear memory. The problem is avoidable in some way? – Nicola Jul 8 '15 at 16:08
• I don't think you can avoid marking nodes as seen – sds Jul 8 '15 at 16:10
• @Nicola If you don't want to use a separate set, you need to redefine nodes so that they have a `visited` flag (e.g. CLOS slot, property lists). You'd need to clean up the flag when returning from `depth-search`. – coredump Aug 21 '15 at 19:14