Ich habe ein Tutorial in OCaml gemacht (frag mich nicht, warum, ich habe mich gerade entschieden, meine Sprachkenntnisse zu erweitern, denke ich) und ich bin an den Punkt gekommen, wo ich bin Arbeiten mit Graphen. Das Tutorial hat mir gezeigt, wie man eine Breitensuche in einem Graphen durchführt, was ich gut umsetzen kann. Ich habe jedoch mit einem Algorithmus für eine Tiefensuche gekämpft, was eines der Dinge ist, in denen das Tutorial sagt: "Wir empfehlen Ihnen, dies auf einer Tiefenmethode zu versuchen, aber wir werden Ihnen nicht sagen, wie TU es."OCAML Tiefensuche
Ich versuche es so zu implementieren: let rec dfs graph start end
. Das heißt, ich habe versucht, es zu tun, wo ich eine Liste von Kanten(), einen Startknoten (start
) und einen Endknoten (end
) nehme.
Ich habe meine Graph mit einer Liste von Kanten erstellt ...
let edges = [
("a", "b"); ("a", "c");
("a", "d"); ("b", "e");
("c", "f"); ("d", "e");
("e", "f"); ("e", "g")
];;
Allerdings bin ich verlor völlig darüber, wo man von hier geht. Irgendwelche Ratschläge, wie man mich in Gang bringt? Vielen Dank.
Die übliche Ein-Satz-Zusammenfassung ist, dass die Tiefensuche die gleiche wie die Breitensuche ist, außer dass Sie die Warteschlange der nicht besuchten Knoten durch einen Stapel ersetzen. Sie könnten versuchen, Ihre Breitensuche-Implementierung auf diese Weise zu ändern. –
Eine Funktion zum Auflisten der Nachfolger eines Knotens kann Ihnen die Arbeit erleichtern. – PatJ