Problem with implementing Depth First Search in Scheme

Im trying to implement Depth First Search in Scheme, but I can only get it to partially work. This is my code:

 (define (depth-first-search graph node neighbour path dest)
  (cond ((null? neighbour) #f)
        ((equal? node dest) path)
        ((member (car neighbour) path) (depth-first-search graph node (cdr neighbour) path dest))
        ((memq (car neighbour) (car graph)) (depth-first-search (cdr graph) (car neighbour) (memq (car neighbour) (car graph)) (append path (list (car n开发者_如何学Goeighbour))) dest))
        (else depth-first-search (cdr graph) path dest)))

And this is my graph, data structure:

  (define complete-graph
  '((a b c d e)
    (b a c)
    (c a b f)
    (d a e h)
    (e a d)
    (f c g i)
    (g f h i j) 
    (h d g j)
    (i f g j)
    (j g h i)))

This is how I call the procedure:

(depth-first-search complete-graph (caar complete-graph) (cdar complete-graph) (list (caar complete-graph)) 'd)

To procedure shoud return the full path frome the start-node to the dest(ination) as a list, but it only seems to work with some start and destination nodes. If I start with 'a and 'c, it returns the right list '(a b c), but if I try with 'a and 'd, I get #f in return. So it probably is something wrong with the backtracking in the algorithm. But I have looked at the code for too long, and I really can't find the problem..

---

Assuming node 'a has children '(b c d e), node 'b has children '(a c), node ... First you need a function that expands a node to its children.

(define (expand graph node)
  (let ((c (assq node graph)))
    (if c (cdr c) '())))

Second: you have to remember all visited nodes. In general hat is different from the path (maybe it does not matter in this example). Third: you need to remember all nodes you want to visit (result from the node expansion process). So define a helper function

(define (dfs* graph visited border path dest)

If there are no nodes left to visit, then no road exist.

  (cond ((null? border) #f)

If the first element in border is equal to our destination, then we are happy

        ((eq? (car border) dest) (cons (car border) path))

Lets check all visited nodes. If the first node in border was visited before then proceed without node expansion

        ((memq (car border) visited)
         (dfs* graph visited (cdr border) path dest))

Otherwise expand the first node of border

        (else (dfs* graph
                   (cons (car border) visited)
                   (append (expand graph (car border)) (cdr border))
                   (cons (car border) path)
                   dest))))

Call that helper function with starting values for visited, border and path:

(define (dfs graph src dst)
  (dfs* graph '() (list src) '() dst)

For breath first search: append the expanded node at the end of border

Edit: a) visited and path are the same, you can drop one of them b) the path is returned in reverse order c) The procedure is not correct, path contains all visited nodes. But a post processing of the result of dfs* will do the job.

---

You don't want to change the graph as you do the depth-first search, just the current node. If you want to do things purely functionally, have your function look like:

(define (depth-first-search graph node dest path)
  (let dfs ((node node) (path path))
    (let ((recur (lambda (node) (dfs node (cons node path)))))
      ; Write code here
      ; Recursive calls should use recur, not dfs or depth-first-search
      ...)))

(returning a path or #f as the result). You can use ormap (in Racket or SRFI-1) to iterate through all neighbors of a node, returning the first value that is not #f.