方案深度優先搜索圖形函數

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) 

您可以採用這種技術用於您的目的嗎？