Hallo,
bin gerade mittelschwerwiegend verwirrt. Bitte betrachtet mal bitte: https://de.wikipedia.org/wiki/Tiefensuche#Algorithmus_.28formal.29 , 14.10.2016
die Knoten werden “durchlaufen”. Das ist nicht das Problem. Der Zielknoten wird gefunden.
Wie speichert man sich den Weg bis zum Zielknoten? Welche Datenstruktur oder welche Strukturen wie hinzufügen usw.?
Eine einfache Ausgabe, reicht in dem Fall nicht. Danke für einen Denkanstoß.
Das kann sich zum Beispiel bei einem Baum aus der Datenstruktur ergeben, wenn in jedem Knoten der Parent angegeben wird.
Ansonsten kann man auch den Pfad mitgeben.
DFS(node, goal, path)
{
if (node == goal) {
return Result(node, path);
} else
{
stack := expand (node)
while (stack is not empty)
{
node' := pop(stack);
path' := append(node, path)
DFS(node', goal, path');
}
}
}
oder Rekursiv, wenn ein Knoten gefunden wurde, alles bis zum Root ausgeben.
DFS(node, goal)
{
if (node == goal) {
return node;
} else
{
stack := expand (node)
while (stack is not empty)
{
node' := pop(stack);
result := DFS(node', goal);
if(result not null) {
print(node)
return result;
}
}
}
}
Hoffe die Idee dahinter wurde klar
Die gesuchte Datenstruktur ist formal der Stack (also LIFO), in dem die einzelnen Knoten gespeichert werden. In der Praxis würde ich es mit einer (Array-)List umsetzen.
Edit: Die Begriffe tauchen in der Art ja auch in ionutbaiu’s Code auf.
Okay, hab ich kapiert…
“einem Baum aus der Datenstruktur ergeben” - das funktioniert leider nicht, es (<- ungenau, ich weiß*) ist >kein< Baum, es (<- DFS) ist auch kein DFS im eigentlichen Sinne**.
private static LinkedList<String> weg2 = new LinkedList<>();
//...
weg1.add(edge.s2.substring(0, 3));
weg2.add(weg1.toString());
System.out.println("etwas wichtiges für Debug");
depth(/* Argumente (mit edge.s2) */); // rekursiver Aufruf
weg1.removeLast();
//...
System.out.println("");
for (String string : weg2) { // wenn DFS "durchgelaufen" ist
System.out.println(string);
}
System.out.println("");```
funktioniert für DFS.
3. Bei der >Breitensuche< bin ich völlig überfragt. Wie funktioniert es da?
*: Es ist kein [DAG](https://en.wikipedia.org/wiki/Directed_acyclic_graph), das Problem(chen).
**: Da es kein DAG ist, ist es (strenggenommen) auch keine Tiefen**[U]suche[/U]**. Was ich da mache, geht ja in Richtung [Tree traversal](https://en.wikipedia.org/wiki/Tree_traversal) (siehe r.: "search algorithms").*** Aber auch ohne korrekte Bezeichnung , weißt du, was gemeint ist.
----
Also meine Frage wäre jetzt, was ich bei der Breitensuche "hinzufügen" muss, um so eine Ausgabe wie oben zu erhalten. Also bei Breitensuche brauche ich auch einen Denkanstoß.
***: Das soll jetzt kein Buzzword-Bingo (und/oder URL-Bingo) werden.Um was für eine Datenstruktur handelt es sich?
Ist es eine Liste?
Ist es ein Baum?
Ist es ein Graph?
Ist es ein Graph mit Zyklen?
Wenn man Breitensuche mit Pfad umsetzen möchte, dann braucht es ein bisschen mehr Datenstruktur.
Genauer gesagt nimmt man sich eine Map<Node, List> paths und eine List toInspect.
paths.put(start, emptyList());
while(!toInspect.isEmpty()) {
Node current = toInspect().get(0);
toInspect.remove(0);
if(current.equals(target)) {
print(current, paths.get(current));
//Hier evtl. abbrechen, wenn nur der erste Treffer ausgegeben werden soll.
}
List<Node> pathToCurrent = paths.get(current);
for(Node node: getNeighboursOf(current)) {
if(!paths.getKeys().contains(node)) {
List<Node> pathToNode = new ArrayList(pathToCurrent);
pathToNode.add(current);
toInspect.add(node);
paths.put(node, pathToNode);
}
}
}```Hat sich schon erledigt meine Frage. Danke für jeden Hinweis.
Also sorry, dass ich das so „abgewürgt“ hab, aber über den Problemgraph möchte ich nicht sprechen. Der Hinweis von @ionutbaiu war aber viel Wert - mit LinkedHashMap (das ist keine NavigableMap oder SortedMap, wie vielleicht anzunehmen) hat es toll funktioniert. 
Edit: Wer doch noch etwas über das Problem/den Problemgraph wissen möchte, der schreibt mir einfach eine PN - ich beantworte sie dann (u. a.) mit mehreren Zeichnungen dazu.