Ich schreibe eine Funktion in Scheme mit Advanced Student-Einstellungen. Die Funktion durchläuft das Diagramm G und schaut, ob es einen Pfad zwischen dem Knoten X und Y gibt. Es funktioniert "irgendwie", aber nicht in allen Fällen. Ich weiß, wo das Problem liegt, aber ich bin mir nicht sicher, wie ich es beheben soll. Zuerst schaue ich, ob der Scheitelpunkt X, auf den ich schaue, besucht wurde, wenn nicht, fahre ich fort und markiere ihn als besucht. Dann gibt es die Funktion find-adju. Diese Funktion gibt eine Liste aller Nachbarn für einen gegebenen Eckpunkt zurück. Zum Beispiel, wenn ich hatte eine grafische Darstellung wie folgt aus:Wie wird die Prozedur für jedes Element in einer Liste in Scheme iteriert?
(define-struct graph (vertices edges))
(define-struct vertice (name visited))
(define-struct edge (start-vertice end-vertice length))
(define vertices-list
(list (make-vertice 0 0)
(make-vertice 1 0)
(make-vertice 2 0)
(make-vertice 3 0)
(make-vertice 4 0)
)
)
(define edges-list
(list (make-edge 0 1 0)
(make-edge 0 2 0)
(make-edge 1 3 0)
(make-edge 2 0 0)
(make-edge 2 4 0)
(make-edge 4 2 0)
)
)
(define G (make-graf vertices-list edge-list))
(traverse-graph? 0 4 G)
Dann für gegebenen Knoten 0 würde zurückkehren Liste (1 2). Als nächstes schaue ich mir die Liste an und frage, ob mein gewünschter Vertex Y darin ist. Wenn nicht, suchen Sie erneut rekursiv nach dem ersten Element in der Liste. Aber dabei verliere ich Informationen über alle anderen Nachbarn. Im selben Fall würde es den Knoten 1 betrachten, alle seine Nachbarn finden und dann würde die Prozedur aufhören, weil sie keinen Weg gefunden hat. Aber der Scheitelpunkt 2 bleibt dann unbesucht. Wie kann ich den Prozess auf jeden Artikel in der Lsit und nicht nur auf den ersten schauen lassen?
(define (traverse-graph X Y G)
(cond
[(not(eq? (vertex-visited (find-vertex X (graph-vertices G))) VISITED))
(begin
(set-vertex-visited! (find-vertex X (graph-vertices G)) VISITED)
(cond
[(member Y (find-adju X (graph-edges G))) #t]
[(not (empty? (find-adju X (graph-edges G)))) (traverse-graph (car (find-adju X (graph-edges G))) Y G) ]
[else #f]
)
)
]
[else #f]
)
)
dachte ich vielleicht die ganze Liste mit cdr Rückkehr statt Auto in die Traverse-Funktion, aber ich weiß nicht, wie das realisieren. Und wie würde ich mit dem ersten Schritt umgehen, wo X eine Zahl und keine Liste ist.
EDIT:
I for-each versucht, das Hinzufügen, das in Ordnung zu sein scheint zu funktionieren, aber das Ergebnis ist mir nichts zu geben. Kein wahr oder falsch. Wenn ich es Schritt für Schritt zu debuggen, sehe ich, dass es wahrscheinlich richtig überquert, aber wenn es das erreicht [(Mitglied Bedingung, stoppt er, ohne irgendetwas zurückkehrt, auch wenn die Bedingung erfüllt ist.
(define (traverse-graph X Y G)
(cond
[(not(eq? (vertex-visited (find-vertex X (graph-vertices G))) VISITED))
(begin
(set-vertex-visited! (find-vertex X (graph-vertices G)) VISITED)
(cond
[(member Y (find-adju X (graph-edges G))) #t]
[(not (empty? (find-adju X (graph-edges G))))
(for-each (lambda (h)
(traverse-graph h Y G)
) (find-adju X (graph-edges G))
)
]
[else #f]
)
)
]
[else #f]
)
)
Ich habe irgendwie verloren. Können Sie mir einen genauen Code zeigen? – Arcane