图函数的深度优先搜索

Question

这是一个家庭作业问题，我正在尝试在Scheme中执行深度优先搜索功能，这是我到目前为止编写的代码：

(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'是当前节点
“访问”是一个列表，我跟踪我访问过的节点
'nextNode' 是一个函数，返回第一个未访问的邻居（如果有的话），否则返回#f
'成员？'测试节点是否在访问列表中

图形表示使用相邻节点，通过使用letrec对节点的引用来制作，这就是我在“邻居”中使用force的原因： 例如：
(letrec ([node1 (list "NY" (delay (list node2 node3))))]，其中node2和node3被定义为node1

我正在处理的问题是我访问的列表失去了对我的一些节点的跟踪当我退出递归时访问了，我该如何解决这个问题？

Answer 1

您必须从递归调用中获取新的访问列表作为返回值。您要么必须修改explore，以便它返回其访问过的列表，要么定义一个您递归而不是explore的辅助函数。然后，在递归之后，您必须使用函数返回的新访问列表。

编辑：
也许更好的方法是重组你的职能。我认为这比需要的更复杂。你只是在进行深度优先遍历，对吧？真的不是搜索吗？您可以尝试更像这样的方法，使用显式堆栈来跟踪要访问的节点以及访问的节点列表：

(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

我也在此处回答了。

执行此操作的一种方法是仅返回列表，以便您可以在更高级别的递归中访问它。

另一种方法是将列表存储在递归之外的变量中。换句话说，不存储在堆栈中。由于为此使用全局变量不是一个好主意，因此我们需要一些局部递归。

下面的代码是反转列表的愚蠢方法，但它确实说明了我正在讨论的技术。

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

您可以采用这种技术来达到您的目的吗？