Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Blatt 12 - Graphendurchlauf 12.5
Hey,
ich wollte mal nachfragen, ob jemand mir kurz erklären kann, was die Methoden next() und hasNext() genau machen sollen. Soll bei next() der nächste Nachfolger eines Knotens ausgegeben werden? Das geht doch garnicht, weil ich dazu speziell den Knoten wissen müsste, um den es sich handelt und der weder als Parameter noch sonst irgendwie angegeben wird. Dasselbe Problem stellt sich bei mir bei hasNext().
Und in welcher Methode wird denn dann tatsächlich die Tiefensuche ausgeführt?
Muss ich da selber eine erstellen? Weil prinzipiell ist ja keine vorhanden.
Wäre lieb, wenn mir jemand von euch erklären kann, was ich denn jetzt genau in der Aufgabe machen soll 
Ich weiß, dass es sich um Tiefen- und Breitensuche handelt, aber mit den gegebenen Methoden und der Aufgabenstellung komme ich nicht wirklich zurecht.
Danke im Voraus!
Der Startkonten wird dir im Konstruktor uebergeben. Den musst du dann zwischenspeichern, um darauf zugreifen zu koennen, wenn der Graph traversiert werden soll. Dafuer hast du in beiden Klassen einen Stack bzw. eine Queue gegeben. hasNext() soll wahr sein, wenn es noch Knoten gibt, die nicht besucht wurden. next() soll den naechsten Knoten (nach DFS/BFS) ausgeben. Rein prinzipiell kannst du die Iteration in next oder hasNext() implementieren, aber ich weiß nicht, was erwartet wird. Ich vermute mal in der next-Methode waere es angebrachter.
Wenns den Thread jetzt schon mal gibt: Wie wird erwartet, dass die Knoten in der ‘Arbeitsliste’ abgelegt werden? Im DFS-Iterator speichere ich den naechsten Knoten momentan in einer extra Instanzvariable, aber im BFS-Iterator als Kopf der Queue? Prinzipiell waere das ja egal, aber ich hab das Gefuehl in den Testfaellen wird das abgeprueft und das geht (fuer mich) nicht aus der Aufgabenstellung hervor…
Das wird in den Übungsfolien gut gezeigt. Einmal wie bei der Tiefensuche auf den stack die neuen Knoten gelegt und genommen werden und einmal wie auf die queue in der Breitensuche zugegriffen wird.
here you go: https://www2.cs.fau.de/teaching/WS2014/AuD/uebungen/secure/uebung12_handout.pdf#page=71&zoom=auto,-390,6
Das ganze klappt aber nach meinem Verstaendnis nicht, da folgendes in der Angabe steht: “Ein Knoten gelten dann als besucht, wenn sie in die Arbeitsliste Aufgenommen wurden.” Also muessten soweit ich das verstehe, ein Knoten als besucht markiert werden, sobald er auf den Stapel kommt… so stehts zumindest da :p. Auf den Uebungsfolien werden aber bei der Abarbeitung eines Knotens alle adjazenten Knoten eingefuegt, womit diese nach Aufgabe aber als besucht markiert werden muessen. Ausserdem wird bei Folie 93. Die 6 mit in den Stapel aufgenommen, obwohl noch nicht klar ist, ob von wo diese besucht wird. Wäre bspw. noch ein Knoten X von 7 erreichbar, der zwischen 4. und 6. liegt, so waere die Reihenfolge im Stapel ja: 6X4, damit ist 6 aber ueber 4 vor X erreichbar, liegt aber nach X im Stack.
Mal ein Beispiel:
G(V, E): V = {A,B,C,D },
E = { (A, B), (A,D), (A,C),
(B,C) } ( gerichtet von A->B usw.)
Von links nach rechts, startend von A.: ( sei rechts das obere Element im Stack )
Arbeite Knoten A ab: Stack= CDB → besucht = {A,C,D,B}
Arbeite Knoten B ab: Stack = CD?? eigentlich kommt jetzt C, aber das ist schon mal auf den Stack gelangt, wodurch es als besucht markiert werden muesste.
Da wäre dann schon mein Problem.
Dazu kommen noch 2 Fragen die mir einfallen: “ein besuchter Knoten darf nicht in die Arbeitsliste aufgenommen werden.” Soll das heißen, dass die Schnittmenge zwischen Arbeitsliste und Knoten immer! leer sein muss oder nur, dass wir einen besuchten Knoten nicht noch ein zweites Mal aufnehmen duerfen?
Bei meiner momentanen Implementierung wird ein Knoten, welcher gerade ausgegeben wird, in den Stack aufgenommen und dann markiert, sowie der naechste Knoten in der Reihe gefunden. Ist das der Aufgabe nach korrekt oder solls anders implementiert werden?
Ja und das werden sie auch. Deswegen werden diese Knoten im späteren Verlauf auch nicht erneut auf den Stack gelegt.
Das als besucht Markieren ist quasi eine Art Merker, damit du einen Knoten nicht mehrfach abarbeitest. Würdest du einen Knoten mehrfach auf den Stack legen können, würdest du manche Knoten auch mehrfach besuchen. Daher markierst du einen Knoten als besucht, sobald du ihn auf den Stack gelegt hast und gehst damit sicher, dass der Knoten wirklich nur einmal besucht wird. „Besucht“ bedeutet also in diesem Fall nicht „bearbeitet“. Die Bearbeitung kommt dann später wenn der entsprechende Knoten wieder vom Stack bzw. aus der Queue entnommen wird. Das sollte auch die Frage deines Beispiels und die weiten Fragen klären. Wenn ein Knoten einmal eingefügt wurde, wird er künftig einfach nicht mehr betrachtet, da er auf jeden Fall noch bearbeitet werden wird oder schon bearbeitet wurde.
Okay danke schon mal. Koenntest du mir aber noch sagen, ob das so stimmt:
Knoten: a, b, c, d.
Kanten:
a-> b, a-> c, a-> d
b-> d
d-> c
- Stack: a
- Stack: dcb , Ausgabe: a
- Stack: dc, Ausgabe: b
- Stack: d, Ausgabe: c
- Stack: , Ausgabe d
Konntest du die Aufgabe mittlerweile lösen?