2016-04-29 24 views
5

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.

+3

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. –

+1

Eine Funktion zum Auflisten der Nachfolger eines Knotens kann Ihnen die Arbeit erleichtern. – PatJ

Antwort

2

Also, ich habe es getan, aber ich finde es seltsam, dass Sie eine Grafik als eine Liste darstellen, wenn Sie darin suchen müssen. Eine Karte wäre viel besser. Wie auch immer, hier ist, wie es gemacht wird:

let edges = [ 
    ("a", "b"); ("a", "c"); 
    ("a", "d"); ("b", "e"); 
    ("c", "f"); ("d", "e"); 
    ("e", "f"); ("e", "g") 
];; 

let successors n e = 
    List.map (fun (_, v) -> v) (List.filter (fun (u, _) -> n = u) e) 

let dfs graph start f = 
    let rec rdfs visited node = 
    if not (List.mem node visited) then 
     begin 
     f node; 
     let s = successors node graph in 
     List.fold_left rdfs (node::visited) s 
     end 
    else visited 
    in rdfs [] start 

let() = let _ = dfs edges "a" print_string in() 

Das erste, was ein successors Funktionen definieren, die Sie jeden direkten Nachfolger eines Knotens geben (der List.filter Teil bekommt man die Kanten, die List.map Teil in zwei Teile, die die resultierenden Kanten gespalten und behalten Sie nur die zweite (die erste ist natürlich der Knoten, für den Sie die Nachfolger suchen).

Die Funktion dfs definiert eine interne Funktion, die zwei Dinge tun, überprüfen, ob der Knoten, an dem wir arbeiten, bereits besucht wurde oder nicht

  • Wenn ja, ändert sich nichts, wir geben nur die gleiche Liste der besuchten Knoten zurück (und vielleicht noch andere Dinge, je nachdem, was Sie mit Ihrer Suche machen wollen).
  • Wenn nein, dann

    • Wir wenden die Funktion, die wir zu dfs auf den aktuellen Knoten gab,
    • Wir diesen Knoten zu den besuchten Knoten hinzufügen,
    • Wir seine Nachfolger nehmen,
    • Wir wenden die Funktion auf jeden an, (hier gibt es einen kleinen Trick, denn wir haben

      List.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

      und

      rdfs : string list -> string -> string list

      statt schreiben

      List.fold_left (fun visited node -> rdfs visited node) ...

      wir können

      List.fold_left rdfs ...

      (etwas mit diesem seltsamen, was zu tun genannt Lambda-Kalkül und einige schreiben Regel eta Umwandlung genannt, die besagt, dass:

      λ x · ux η u (x ∉ fv(u)) :-P) (fv(u) die freien Variablen von u zu sein) (was es bedeutet, wenn das in OCaml, wenn Sie fun x -> f x schreiben Sie f schreiben stattdessen haben könnte, ist es strikt äquivalent.)

    • wir den besuchten Knoten Liste zurück, in dem alle besuchten Knoten

H wurden hinzugefügt ope, ich habe geholfen.