Iterative DFS

Moderator: Effiziente Graphenalgorithmen

Stefan1992
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 20. Okt 2011 22:38

Iterative DFS

Beitrag von Stefan1992 » 21. Jan 2016 10:44

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

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Iterative DFS

Beitrag von Prof. Karsten Weihe » 21. Jan 2016 12:08

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

Stefan1992
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 20. Okt 2011 22:38

Re: Iterative DFS

Beitrag von Stefan1992 » 21. Jan 2016 12:37

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!

Antworten

Zurück zu „Effiziente Graphenalgorithmen“