Scheme Depth-first search of a graph function

Question

This is a homework question,I'm trying to do a Depth-first search function in Scheme,Here's the code I've written so far:

(define explore
(λ(node visited)
  (let* ([neighbors             (force (cdr node))]
         [next        (nextNode visited neighbors)]
         [is-visited        (member? node visited)])

    (cond

      ;if I have no unvisited neighbours print current node and go up one level
      [(equal? next #f)
       (begin
         (display (car node))
         (display " "))]

      ;if current node is not visited and I have unvisited neighbors
      ;print current node,mark as visited and visit it's neighbors
      [(and (equal? is-visited #f) (not (equal? next #f)))
       (begin
         (display (car node))
         (display " ")
         (explore next (cons node visited)))])

    ;go and visit the next neighbor
    (if (not (equal? (nextNode (cons next visited) neighbors) #f ))
     (explore (nextNode (cons next visited) neighbors) (cons node visited))))))  

'node' is the current node
'visited' is a list in witch I keep track of the nodes I visited
'nextNode' is a function that returns the first unvisited neighbor if any or #f otherwise
'member?' test's if a node is in the visited list

The Graph representation is using adjacent made using references to nodes with letrec so that's why I use force in 'neighbors': Eg:
(letrec ([node1 (list "NY" (delay (list node2 node3)))],where node2 and node3 are defined as node1

The problem witch I'm dealing with is that my visited lists looses track of some of the nodes I visited when I come out of recursion,How can I fix this ?

Answer 1

You have to get the new visited list as a returned value from your recursive calls. You'll either have to modify explore so that it returns its visited list, or define a helper function that you recurse on instead of explore. Then after you recurse, you'll have to use the new visited list that the function returns.

EDIT: Perhaps a better way would be to just restructure your function. I think it's more complicated than it needs to be. You're just doing a depth-first traversal, right? Not really a search? You could try something more like this, using an explicit stack to keep track of nodes to visit, and a list of nodes visited:

(define dft
  (lambda (graph)
    (helper graph '(1) '())))

(define helper
  (lambda (graph stack visited)
    (if (empty? stack)
      '() ;we're done. you've got a nice list of visited nodes now, what will you do with it? Return it?
      (let ([currentNode (car stack)])
        (if (member? currentNode visited) 
            (helper graph 
                    ;what do you think the next two parameters are?
                    )
            (begin
              (display currentNode)
              (helper graph 
                      ;what do you think the next two parameters are?
                      ))))))

Since this is a homework problem, I've left the two parameters for the helper function for you to fill in. The nicest thing about this approach is that it's very simple to change it to a breadth-first traversal.

Here's a hint: the parameters for the two different cases will be slightly different.

Answer 2

I answered here as well.

One method of doing this is just to return the list so you have access to it at higher levels of recursion.

Another method is to have your list be stored in a variable outside of the recursion. In other words not stored on the stack. Since it is not a good idea to use a global variable for this we need to have some local recursion.

The following code is a foolish way to reverse a list but it does illustrate the technique I am talking about.

(define (letrecreverse lst)
  (letrec ((retlist '())
           (reverse (lambda (lst)
                      (if (null? lst)
                          '()
                          (begin
                            (set! retlist (cons (car lst) retlist))
                            (reverse (cdr lst)))))))
    (reverse lst)
    retlist))

(letrecreverse '(1 2 3 4))
;outputs '(4 3 2 1)

Can you adopt this technique for your purposes?