Scheme Depth-first search of a graph function
- by John Retallack
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 ?
