Depth-first search

[Stefan1992]

Hallo,

verstehe ich das richtig, dass der iterative Algorithmus der Tiefensuche beim vollständigen Traversieren eines Graphen tatsächlich jede einzelne Kante des Graphen betrachtet, auch wenn er jeden Knoten schon einmal gesehen hat?

Grüße

[Prof. Karsten Weihe]

verstehe ich das richtig, dass der iterative Algorithmus der Tiefensuche beim vollständigen Traversieren eines Graphen tatsächlich jede einzelne Kante des Graphen betrachtet, auch wenn er jeden Knoten schon einmal gesehen hat?

Ja, sicher, denn vor der Betrachtung einer Kante ist ja nicht klar, ob sie zu einem schon gesehenen oder zu einem noch nicht gesehenen Knoten zeigt. Oder habe ich Ihre Frage falsch verstanden?

KW

[Stefan1992]

Nein danke. Das beantwortet meine Frage.

[Stefan1992]

Hallo,

ich habe immer noch ein paar Probleme mit dem Algorithmus.

Mir machen ein wenig die symmetrischen Kanten zu schaffen.

Erst einmal etwas Grundlegendes:

Angenommen ich habe drei Knoten \(v_1, v_2, v_3\) und dazugehörige Kanten \((v_1, v_2), (v_2, v_1), (v_1, v_3)\).

Dann gehe ich davon aus, dass der Pfad \((v_1, v_2, v_1, v_3)\) kein korrekter Pfad von \(v_1\) zu \(v_3\) ist, da laut Definition ein Pfad aus unterschiedlichen \(v_i\) besteht.


Als nächstes etwas schwieriger mit einem Beispiel: Findet die Tiefensuche jeden möglichen Pfad von einem Start- zu einem Zielknoten?
Angenommen ich habe die Knoten \(v_1, v_2, v_3, v_4\) und dazugehörige Kanten \((v_1, v_2), (v_1, v_3), (v_1, v_4), (v_2, v_3), (v_2, v_4), (v_3, v_4)\). Alle Kanten sind symmetrisch, was aber für meine Frage unwichtig ist.
Der angegebene Graph ist im Anhang zu sehen. Die Knoten 1 - 4 sind dabei von links nach rechts durchzunummerieren. Der Startknoten ist dabei \(v_4\) und der Zielknoten \(v_2\).
Wenn ich das richtig sehe, sind die folgenden vier Pfade alle möglichen Pfade, um vom Start- zum Zielknoten zu gelangen:
\((v_4, v_2)\),
\((v_4, v_1, v_2)\),
\((v_4, v_3, v_2)\) und
\((v_4, v_1, v_3, v_2)\)
wohlgemerkt ohne Zyklen auf dem Pfad zu erzeugen.

Das Problem, das ich sehe, ist die Betrachtung des Pfades \((v_4, v_1, v_3, v_2)\). Soll im Anschluss daran der Pfad \((v_4, v_3, v_2)\) "gefunden" werden, besucht der Algorithmus zunächst die Kante \((v_4, v_3)\), kann aber dann nicht mehr zu \(v_2\) weitergehen, da diese Kante vorher bereits besucht wurde.

Das Problem, das ich damit im weiteren sehe, ist das Auslassen eines möglichen fluss-erhöhenden Pfades.

Ich hoffe, ich habe meine Probleme einigermaßen verständlich formuliert. Ich finde leider nicht den Fehler in meiner Implementierung und damit in meiner Denkweise.

[Prof. Karsten Weihe]

Angenommen ich habe drei Knoten \(v_1, v_2, v_3\) und dazugehörige Kanten \((v_1, v_2), (v_2, v_1), (v_1, v_3)\).
Dann gehe ich davon aus, dass der Pfad \((v_1, v_2, v_1, v_3)\) kein korrekter Pfad von \(v_1\) zu \(v_3\) ist, da laut Definition ein Pfad aus unterschiedlichen \(v_i\) besteht.

Man kann Pfade so allgemein definieren, dass dies noch ein Pfad ist, oder so eingeschränkt, dass dies kein Pfad ist. Für unsere Zwecke - insbesondere bei der Programmieraufgabe - macht es wenig Sinn, so etwas als möglichen Pfad mitzubetrachten.

Als nächstes etwas schwieriger mit einem Beispiel: Findet die Tiefensuche jeden möglichen Pfad von einem Start- zu einem Zielknoten?

Nein. Zunächst einmal findet Tiefensuche genauso wie Breitensuche nur einen einzigen Pfad vom Startknoten \(s\) zu jedem anderen Knoten \(v\), und die Vereinigung aller dieser Pfade ist die Arboreszenz, die von der Suche konstruiert wird. Für jeden Knoten \(w\) mit \((w,v)\in A\) bekommt man natürlich schnell noch einen weiteren Pfad, nämlich der Pfad von \(s\) nach \(w\) plus \((w,v)\), aber das war's dann auch schon.

Klärt das Ihre Frage?

KW