Page 1 of 1

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

PostPosted: Wed Jul 08, 2015 12:21 pm
by fibonacci
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) where 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