Ich versuche eine saubere Methode zu finden, einen Graphen im Scala-Stil zu durchlaufen, vorzugsweise mit vals und unveränderlichen Datentypen.
Gegeben die folgende Grafik,
%Vor% Ich möchte, dass die Ausgabe die erste Traversierung der Tiefe ist, die in einem bestimmten Knoten beginnt. Beginnend in 1 zum Beispiel, sollte zum Beispiel 1 2 3 0 4 ergeben.
Ich finde nicht, dass ich einen netten Weg finde, dies ohne veränderbare Sammlungen oder Variablen zu tun. Jede Hilfe wäre willkommen.
Dies ist eine Variante, denke ich:
%Vor%Aktualisiert : Dies ist eine erweiterte Version. Hier falte ich links über die Elemente der Map, beginnend mit einem Tupel einer leeren Liste und Nummer 1. Für jedes Element überprüfe ich die Größe des Graphen und erstelle ein neues Tupel entsprechend. Die resultierende Liste erscheint in umgekehrter Reihenfolge.
%Vor%Ich weiß nicht, ob Sie nach 6 Jahren immer noch nach einer Antwort suchen, aber hier ist es:)
Es gibt auch eine topologische Ordnung und Zyklizität des Graphen zurück: -
%Vor% Scheint, dass diese Frage mehr involviert ist, als ich ursprünglich dachte. Ich habe eine andere rekursive Lösung geschrieben. Es ist immer noch nicht rekursiv. Ich habe mich auch bemüht, es zu einem Einzeiler zu machen, aber in diesem Fall wird die Lesbarkeit sehr darunter leiden. Deshalb habe ich beschlossen, dieses Mal einige val s zu deklarieren:
In meiner vorherigen Antwort habe ich versucht, alle Pfade von dem gegebenen Knoten in dem gerichteten Graphen zu finden. Aber es war falsch nach den Anforderungen. Diese Antwort versucht, gerichteten Kanten zu folgen, aber wenn es nicht möglich ist, dann braucht es nur einen noch nicht besuchten Knoten und fährt von dort fort.
Tenshi,
Ich habe Ihre Lösung nicht vollständig verstanden, aber wenn ich mich nicht irre, ist die Komplexität der Zeit mindestens O (| V | ^ 2), da die folgende Linienkomplexität O (| V |) ist:
%Vor%Nämlich ein Element rechts von einer Liste anzuhängen.
Außerdem ist der Code nicht tail rekursiv, was ein Problem darstellen kann, wenn beispielsweise die Rekursionstiefe durch die von Ihnen verwendete Umgebung begrenzt ist.
Der folgende Code löst einige DFS-bezogene Graphprobleme in gerichteten Graphen. Es ist nicht der eleganteste Code, aber wenn ich mich nicht irre, ist es:
Der Code:
%Vor%Marimuthu Madasamys Antwort funktioniert tatsächlich.
Hier ist die generische Version davon:
%Vor% Hinweis: Sie müssen sicherstellen, dass die Instanzen von T korrekt equals und hashcode implementieren. Die Verwendung von Fallklassen mit primitiven Werten ist eine einfache Möglichkeit, dorthin zu gelangen.
Tags und Links scala graph-traversal