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

Question

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

• amon: You want a Set rather than a List for the visited nodes. Common set representations are Red–Black Trees or Hash Tables.

Answer 1

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))))

• Nick: 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?
• sds: I don't think you can avoid marking nodes as seen
• coredump: @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.