Seite 1 von 1

Depth-first search

Verfasst: 21. Jan 2016 00:31
von 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

Re: Depth-first search

Verfasst: 21. Jan 2016 11:56
von Prof. Karsten Weihe
Stefan1992 hat geschrieben: 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

Re: Depth-first search

Verfasst: 21. Jan 2016 12:32
von Stefan1992
Nein danke. Das beantwortet meine Frage.

Re: Depth-first search

Verfasst: 26. Jan 2016 00:56
von 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.

Re: Depth-first search

Verfasst: 26. Jan 2016 15:25
von Prof. Karsten Weihe
Stefan1992 hat geschrieben: 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.

Stefan1992 hat geschrieben: 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