Impl. von DFS nachvollziehen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 11:01 Do 10.11.2011 | | Autor: | Wimme |
Hallo,
ich habe hier eine Implementation von Directed DepthFirstSearch, die ich nicht recht nachvollziehen kann. Ihr findet sie auf dem angehängten Bild.
Die rot markierten Funktionen, werden wohl je nach genauer Aufgabe
des Algorithmus etwas angepasst und verschieden implementiert.
Also, meine Fragen:
1. top ist nicht das gleiche wie pop, korrekt? D.h. v wird das oberste Element des Stacks, verbleibt dort jedoch auch gleichzeitig?
2. Wenn (1) jedoch so wäre, dann würde ich ja v vom Stack nicht runternehmen, wenn dort z.B. keine nicht vorher besuchte Kante von ausgeht, und somit in einer Endlosschleife landen?
3. Kann man irgendwie allgemein sagen, welche Knoten zu jedem Zeitpunkt auf dem Stack liegen?
4. Wofür genau brauche ich "incoming[...]"?
Ich denke es würde mir schon sehr helfen, wenn ihr einfach anfangt den Algorithmus irgendwie zu erklären.
[Dateianhang nicht öffentlich]
Ich danke euch!
Wimme
Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
|
|
| |
|
moin Wimme,
Deine Frage scheint zur Hälfte darauf zu beruhen, dass du den Code nicht ganz verstehst und zur Hälfte darauf, dass du noch nicht ganz verstanden hast wie Tiefensuche (deutscher Name für DepthFirstSearch) funktioniert.
Beim ersten Teil kann ich leider auch nicht ganz so viel helfen, beim zweiten schon:
Bei der Tiefensuche hat man zu aller erst mal einen Graphen, der untersucht werden soll.
Meist möchte man ein bestimmtes Element suchen, es gibt aber auch andere Anwendungen; Tiefensuche ist wie du ja selbst gesagt hast recht vielseitig einsetzbar und kann je nach Problemstellung geändert werden.
Beim Durchlaufen des Graphen werden jedem Knoten verschiedene Informationen (je nach Aufgabenstellung) zugeordnet.
Klassiker sind etwa:
- Von wo aus wurde der Knoten entdeckt? (das ist dein incoming)
- Wann wurde der Knoten entdeckt? (die sogenannte discovery-time)
- Wann wurde der Knoten verlassen? (die sogenannte finish-time)
Da bei dir nur der erste eine Rolle zu spielen scheint beschränke ich mich mal darauf.
Nun aber mal zur Frage wie genau das abläuft:
Zuerst wird der ganze Graph auf einen Stack gepackt und incoming wird auf nil gesetzt, das bedeutet die Knoten wurden "noch nicht entdeckt".
Dann geht die richtige Tiefensuche los:
Man nimmt sich einen Knoten aus dem Graphen (also bei dir aus S) und falls dieser (heißt bei dir v) mit einem anderen Knoten aus dem Graphen verbunden ist (heißt bei dir w) so wird die Tiefensuche auf w angewandt.
Ein Problem dabei wäre, dass man ja keine Knoten mehrfach abarbeiten möchte.
Dafür (unter anderem) sind die "incoming" gut.
Wenn w von v aus "entdeckt" wird so wird incoming auf v gesetzt.
Betrachten wir den Knoten w später nochmal und sehen "aha, der wurde bereits entdeckt" brechen wir sofort ab und machen mit dem nächsten Knoten weiter.
Auf diese Art ist gewährleistet, dass keine Knoten mehrfach bearbeitet werden.
Die Tiefensuche hat ihren Namen daher, dass erst auf einem Pfad "in die Tiefe" gegangen wird, bis dieser zu Ende ist; das heißt bis man einen Knoten erreicht hat, der keine unentdeckten Nachfolger mehr hat.
Dann geht man wieder eine Ebene höher und schnappt sich von dem "Elternkonten" den nächsten Unbekannten.
Sollte man ganz oben an der Wurzel angekommen sein so muss der Vollständigkeit halber nochmal geguckt werden ob es nicht noch irgendwo ein paar Knoten gibt, die nicht behandelt wurden, da sie überhaupt nicht mit den bisher behandelten verbunden sind.
Das ganze klingt jetzt vielleicht ein wenig kompliziert, ist es aber eigentlich garnicht.
Guck dir am besten mal die Grafik hier an:
http://de.wikipedia.org/wiki/Tiefensuche
Es wird schön gezeigt und durchnummeriert in welcher Reihenfolge die Knoten besucht werden und man sieht ganz gut, dass erst ein Pfad bis ganz unten durchgegangen wird bevor der nächste besucht wird.
Und nochmal speziell zu deinen Fragen:
Ich finde den Code auch recht komisch und könnte mir da Endlosschleifen durchaus vorstellen, vor allem da ich persönlich die for-each-Schleife komplett durchlaufen lassen würde BEVOR die while beginnt...
Aber was den Code speziell angeht lass ich deine Frage mal halb offen, vielleicht sieht ja jemand einen genialen Sinn darin.^^
lg
Schadow
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:26 Mo 14.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
