方案深度优先搜索图形函数

Question

这是一个家庭作业问题，我试图做方案的深度优先搜索功能，这是我到目前为止已经编写的代码：

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

“节点”是当前节点
“访问”是女巫列表我跟踪我访问了
“nextNode”节点是返回第一个未访问过的邻居，如果任何或#F否则
“成员函数？ “测试的，如果一个节点是在访问列表

的图形表示中利用相邻使用的节点引用与letrec所以这就是为什么我在“邻居”使用发力： 如：
（letrec（[节点1（名单“ NY“（delay（list node2 node3）））]，其中node2和node3被定义为node1

我正在处理的问题是我的访问列表丢失了我访问过的一些节点的轨迹在递归中，我该如何解决这个问题？

Answer 1

你必须得到新的访问列表作为递归调用的返回值，你必须修改e xplore，以便它返回它的访问列表，或定义一个辅助函数，而不是探索。然后在递归后，您将不得不使用该函数返回的新访问列表。

编辑： 也许更好的办法是重组你的功能。我认为它比需要更复杂。你只是在深度优先遍历，对吧？不是真的搜索？你可以尝试更多的东西像这样，使用一个明确的堆栈跟踪节点的访问，并参观了节点列表：

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

由于这是一个家庭作业的问题，我已经离开了两辅助函数的参数供您填写。这种方法最好的一点是，将其更改为宽度优先遍历非常简单。

下面是一个提示：两种不同情况下的参数会略有不同。

Answer 2

我回答了here。

这样做的一种方法就是返回列表，以便您可以在更高级别的递归中访问它。

另一种方法是让您的列表存储在递归之外的变量中。换句话说，不存储在堆栈上。由于使用全局变量不是一个好主意，所以我们需要有一些本地递归。

下面的代码是一个愚蠢的方式来扭转列表，但它确实说明了我正在谈论的技术。

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

您可以采用这种技术用于您的目的吗？