Seite 1 von 1

Iterative DFS

Verfasst: 21. Jan 2016 10:44
von Stefan1992
Hallo,

ich habe bei meiner Recherche einen Algorithmus zur iterativen Tiefensuche gefunden, in dem eine Schleife über alle Knoten durchlaufen wird. Ist der gerade betrachtete Knoten noch nicht gesehen, wird auf diesem Knoten eine normale Tiefensuche aufgerufen.
Widerspricht dies nicht der angegebenen Laufzeit im Wiki? In der äußeren Schleife hat man eine Komplexität von O(|V|). Für jeden betrachteten Knoten hat man dann noch die Worst-case-Laufzeit von (O(|V| + |A|). Somit würde das nach meinem Verständnis eine Laufzeit von O(|V| * (|V| + |A|) = O(|V|^2) ergeben.
Man könnte natürlich argumentieren, dass in der äußeren Schleife die Elemente übersprungen werden, die dann schon mal bei einer Tiefensuche gesehen wurden und somit die Tiefensuche nur noch auf Knoten aufgerufen werden, die nicht zum bereits traversierten Graphen gehören.
Ist das dann richtig?

Grüße

Re: Iterative DFS

Verfasst: 21. Jan 2016 12:08
von Prof. Karsten Weihe
Stefan1992 hat geschrieben: ich habe bei meiner Recherche einen Algorithmus zur iterativen Tiefensuche gefunden, in dem eine Schleife über alle Knoten durchlaufen wird. Ist der gerade betrachtete Knoten noch nicht gesehen, wird auf diesem Knoten eine normale Tiefensuche aufgerufen.
Das klingt für mich eher nach rekursiv als nach iterativ :!: :?: :shock:

Stefan1992 hat geschrieben: Widerspricht dies nicht der angegebenen Laufzeit im Wiki?
DIe Laufz... asymptotische Komplexität im Wiki bezieht sich selbstverständlich ausschließlich auf die Implementation im Wiki und kann daher den realen asymptotischen Komplexitäten anderer, davon offenkundig abweichender Implementationen von vornherein nicht widersprechen. Implementationen desselben Algorithmus können beliebig schlecht sein, das Wiki übernimmt da keine Gewähr. 8)

Allerdings kann ich mir nicht vorstellen, dass Sie eine Implementation gefunden haben, die nicht lineare Laufzeit hat (sofern die Implementation nicht fehlerhaft dargestellt ist).

Stefan1992 hat geschrieben: In der äußeren Schleife hat man eine Komplexität von O(|V|). Für jeden betrachteten Knoten hat man dann noch die Worst-case-Laufzeit von (O(|V| + |A|). Somit würde das nach meinem Verständnis eine Laufzeit von O(|V| * (|V| + |A|) = O(|V|^2) ergeben.
Also entweder explodiert's exponentiell, weil ja in jedem weiteren Vorwärtsschritt dasselbe passiert, oder es bleibt linear.

Stefan1992 hat geschrieben: Man könnte natürlich argumentieren, dass in der äußeren Schleife die Elemente übersprungen werden, die dann schon mal bei einer Tiefensuche gesehen wurden und somit die Tiefensuche nur noch auf Knoten aufgerufen werden, die nicht zum bereits traversierten Graphen gehören.
Ist das dann richtig?
Ein entscheidendes Detail, das Sie leider erst ganz zum Schluss nennen... :roll: :wink:

Dann bleibt es natürlich linear, denn jede Kante wird nur einmal durchlaufen und jeder Knoten nur so häufig gesehen, wie Kanten in ihn hineinzeigen.

KW

Re: Iterative DFS

Verfasst: 21. Jan 2016 12:37
von Stefan1992
Prof. Karsten Weihe hat geschrieben: Das klingt für mich eher nach rekursiv als nach iterativ :!: :?: :shock:
Entschuldigung, ich habe mich falsch ausgedrückt. Ich meinte natürlich die wiederholte Tiefensuche (repeated depth first search). :oops:
Und da ich einen Iterator implementiere, hoffe ich doch stark, dass ich die iterative Variante implementiere. :mrgreen:
Prof. Karsten Weihe hat geschrieben: Ein entscheidendes Detail, das Sie leider erst ganz zum Schluss nennen... :roll: :wink:

Dann bleibt es natürlich linear, denn jede Kante wird nur einmal durchlaufen und jeder Knoten nur so häufig gesehen, wie Kanten in ihn hineinzeigen
Vielen Dank für die Antwort!