Wie schreibe ich meinen Code in Scheme ohne Speichern von Statusinformationen in Strukturen?

Question

Ich spielte in Scheme und ich versuchte ein Prädikat zu erstellen, das mir sagen würde, ob es einen Pfad zwischen zwei Scheitelpunkten in einem gegebenen Graph gibt. Mein Programm verwendet grundsätzlich die Warteschlange, um es herauszufinden. Ich benutze BFS, um durch den Graphen zu gehen, und ich füge alle angrenzenden Scheitelpunkte der Queue hinzu und wenn mein gesuchter Wert in der Queue ist, gebe ich #t zurück. Aber diese Lösung erfordert die Verwendung der Datenstruktur, um alle Informationen zu speichern, und mir ist bewusst, dass das Übergeben der Warteschlange zwischen mehreren Funktionen nicht ideal ist. Wie kann ich meinen Code ändern, ohne die Warteschlange zu verwenden und sie sauberer zu machen? Sie können meinen Code unten sehen.

habe ich diese aproach: http://www.geeksforgeeks.org/find-if-there-is-a-path-between-two-vertices-in-a-given-graph/

(require data/queue) 
(define-struct graph (vertices edges)) 
(define-struct vertice (name visited)) 
(define-struct edge (start-vertice end-vertice length)) 

;I create data for testing here 
(define vertices-list2 
    (list (make-vertice 0 0) 
     (make-vertice 1 0) 
     (make-vertice 2 0) 
     ) 
) 

(define edges-list2 
    (list (make-edge 0 1 0) 
     (make-edge 1 2 0) 
     ) 
) 

;Const for marking a vertice as visited 
(define VISITED 99999) 

(define (reachable? X Y G) 
    (let ((q (make-queue))) 
    (cond 
     [(empty? (graph-edges G)) #f] 
     [(= X Y) #t] 
     [else (bfs-graph X Y G q) ] 
    ) 
    ) 
) 

(define (bfs-graph X Y G q) 
    (cond 
    [(not(eq? (vertice-visited (find-vertice X (graph-vertices G))) VISITED)) 
    (begin 
     (set-vertice-visited! (find-vertice X (graph-vertices G)) VISITED) 
     (find-adj X (graph-edges G) q) 
     (cond 
     [(queue-empty? q) #f] 
     [(memq Y (queue->list q)) #t] 
     [else (bfs-graph (dequeue! q) Y G q)] 
     ) 
     ) 
    ] 
    [(queue-empty? q) #f] 
    [else (bfs-graph (dequeue! q) Y G q)] 
    ) 
) 

(define (find-vertice V vertice-list) 
    (cond 
    [(empty? vertice-list) (error 'find-vertice "Graph does not contain given vertice")] 
    [(eq? V (vertice-name (car vertice-list))) (car vertice-list)] 
    [else (find-vertice V (cdr vertice-list))] 
    ) 
) 

(define (find-adj V edge-list q) 
    (cond 
    [(empty? edge-list) q] 
    [(eq? V (edge-start-vertice (car edge-list))) 
    (begin 
     (enqueue! q (edge-end-vertice (car edge-list))) 
     (find-adj V (cdr edge-list) q)) 
    ] 
    [else (find-adj V (cdr edge-list) q)] 
    ) 
) 

;Run 
(define G (make-graph vertices-list2 edges-list2)) 
;Predicate call 
(reachable? 0 1 G) 

Answer 1

Ich bin nicht sicher, warum Sie nicht wollen, entlang der Warteschlange zu übergeben.

Eine Möglichkeit, die Warteschlange zu umgehen, besteht jedoch darin, die Warteschlange und die Hilfsfunktionen für bfs-graph lokal zu machen.

(define (bfs-graph X Y G) 
    (define q (make-queue)) 
    (define (find-vertice V vertice-list) ...) 
    (define (find-adj V edge-list) ...) 
    (cond 
    [(not(eq? (vertice-visited (find-vertice X (graph-vertices G))) VISITED)) 
    ...] 
    ... as-before ...)) 

PS: Ein Eckpunkt, zwei Ecken