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.
12.7 - dfs()
Versteht jemand was die methode dfs() machen soll?
einfach dfsHelper(0) aufrufen? wohl kaum?
werde aus der aufgabenstellung nicht schlau. !
//
(meine dfsHelper() funktioniert soweit, habe sie mal für beliebige Knoten ausgeführt, abschließense printDFSNum-Ausgabe stimmt auch)
Hatte mir da auch schon die gleichen Gedanken gemacht. Is halt komisch, weil dfs() keinen Startknoten übergeben bekommt. Scheint so, als musst du in die dfs() also deinen Startknoten reinschreiben. Keine Ahnung ob das Absicht ist, weil es wäre kein Problem des zu ändern.
Aber wir könnten zumindest, mal die Ausgabe vom BeispielGraphen vergleichen:
Startknoten = 4:
node 0 has dfsnum 1
node 1 has dfsnum 3
node 2 has dfsnum 2
node 3 has dfsnum 0
node 4 has dfsnum 4
node 5 has dfsnum -1
die -1 scheint mir unsinnig zu sein…
oder soll die für nicht besucht stehen?
wird bei dir mit -1 initialisiert ?
gruss
clemens
node 0 has dfsnum 1
node 1 has dfsnum 3
node 2 has dfsnum 4
node 3 has dfsnum 2
node 4 has dfsnum 0
node 5 has dfsnum 0
Jup, ich dachte mir, dass ich nicht besucht mit -1 mach. Es steht zwar nichts genaues in der Angabe, aber schließlich heißt 0, dass der Knoten als erstes vollständig traversiert wurde.
Aber warum sind bei dir einige Werte vertauscht 
Hab ich da was aus der Angabe falsch verstanden? Da steht doch:
“Diese Nummer soll die Anzahl der Knoten wiedergeben, die vor dem aktuellen Knoten von der Tiefensuche vollständig traversiert wurden.”
Ich hab des so aufgefasst, dass der Knoten erst dann seine Nummer bekommt, wenn man von ihm aus alle möglichen Wege gegangen ist. Und nicht, dass er seine Nummer bekommt, sobald man ihn das erste mal besucht.
bei mir wird beim besuch hochgesetzt.
also noch vor der rekursion… 
denke auch, dass ich richtig liege…
[quote=clebinger]bei mir wird beim besuch hochgesetzt. also noch vor der rekursion…[/quote]Der Hinweis auf die topologische Sortierung sollte deine Frage beantworten… alle Abhängigkeiten eines Knotens müssen erledigt sein, bevor der Knoten selbst erledigt werden kann.
[quote=clebinger]denke auch, dass ich richtig liege…;)[/quote]Und da bist du dir sicher?
Hatte glaub ich noch nen kleinen Fehler drin. Hab jetzt nochmal ne andere Ausgabe;) Wäre nett wenn mir jemand sagen könnte, welche richtig ist. Startknoten ist wieder die 4:
node 0 has dfsnum 0
node 1 has dfsnum 3
node 2 has dfsnum 4
node 3 has dfsnum 1
node 4 has dfsnum 2
node 5 has dfsnum -1
Bei der oberen Lösung werden die Zahlen dann vergeben, wenn für einen Knoten die Rekursion komplett abgeschlossen ist. Jetzt werden die Nummern schon vergeben, wenn von einem Knoten aus gerade die letzte mögliche Kante genommen wird.
This
Danke für den Hinweis…,. Beantwortet allerdings noch nicht die Frage, für was dfs() gut sein soll, bzw. wie sie genau dfsHelper() anstoßen soll.
Kann leider keine Ausgaben mehr posten, weil diese augenblicklich für mich keinen Sinn mehr machen…
dfs() soll alle Werte initialisieren und ggf. zurücksetzen und dfsHelper() mit einem geeigneten Wert aufrufen
Das könnte daran liegen, dass er irgendwo nen Fehler hat
Ich habe das Zeug bisher noch nicht implementiert, allerdings bin ich gerade dabei Tests dafür zu entwickeln.
Für den in der main vorgegebenen Graphen würde ich folgende Lösung als richtig ansehen, für den Startwert 4:
n 0 d 1
n 1 d 3
n 2 d 2
n 3 d 0
n 4 d 4
Wobei man, sollte ein Scherzkeks auf die idee kommen, die adjList von hinten aufzuarbeiten und nicht von vorne, darüber streiten könnte, dass das Ergebnis ganz anders aussieht xD
Ich versteh die Aufgabe so, dass dfs() selbstständig einen (oder mehrere s.u.) geeigneten Knoten raussucht und dann die helper damit aufruft.
Der Knoten 4 ist meiner Ansicht nach ein „geeigneter“ Knoten, weil er die geringste Anzahl an Eltern hat. Aufgrund dessen sollte man auch den Tipp nicht vernachläßig, dass der Graph nicht notwendigerweise zusammenhängen muss => dfs müsste die helper mehrfach aufrufen.
Ich hoffe, dass ich die Aufgabe soweit richtig verstanden habe, sicher bin ich mir da bisher noch nicht xD
Spätestens am Mittwoch nach der Übung kann ich aber mehr dazu sagen hehe
Grüße F
Edit: mir stellt sich auch die Frage, wie ich einen Graphen testen soll, der ungefähr so aussieht:
// dreieck
0 → 1
1 → 2
2 → 0
// zwei Blätter
1 → 3
2 → 4
Was dort der geeignete Knoten ist mir ein Rätsel. Wähle ich 1, dann müsste ja rauskommen:
n 0 d 0
n 1 d 4
n 2 d 2
n 3 d 3
n 4 d 1
Wähle ich 2, sähe es so aus:
n 0 d 2
n 1 d 1
n 2 d 4
n 3 d 0
n 4 d 3
keine Ahnung… was den „geeigneten“ Knoten angeht… bisher klingt das vernünftigste: Kleinste Anzahl an Eltern, Größte anzahl direkter Nachkommen. Sollte es mehrere Knoten geben die drunter fallen, den ersten davon. Wobei das für sehr große Graphen auch trügerisch sein kann… ich warte bis Mittwoch
In der Methode dfs() sollt ihr Eure Datenstrukturen initialisieren und die Hilfsfunktion mit geeigneten Werten aufrufen.
Nach dem Aufruf von dfs() soll jeder Knoten traversiert worden sein. Da (wie in der Aufgabenstellung steht), der Graph nicht zusammenhaengend sein muss (wie der Beispielgraph in der main-Methode), koennten mehrere dfsHelper()-Aufrufe notwendig sein.
Es ist auch egal, mit welchem Knoten ihr den Helper aufruft. Evtl. sind noch mehr Aufrufe notwendig, falls noch nicht alle Knoten traversiert wurden.
Beispiel: A → B
Alternative 1:
Wenn ihr dfsHelper(B) aufruft, bekommt B sofort eine Nummer (keine Kinder!) und kehrt zurueck. Dann muesst ihr noch dfsHelper(A) aufrufen (weil …).
Alternative 2:
Wenn ihr aber dfsHelper(A) aufruft, muss rekursiv erst die Kinder abgearbeitet werden, …, beide Knoten bekommen eine Nummer und es ist kein erneuter dfsHelper-Aufruf in der Methode dfs notwendig.
Mehr dazu in Euren Uebungen.
Dankeschön;)