Depth-first search

Moderator: Effiziente Graphenalgorithmen

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

Depth-first search

Beitrag von Stefan1992 » 21. Jan 2016 00:31

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
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Depth-first search

Beitrag von Prof. Karsten Weihe » 21. Jan 2016 11:56

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

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

Re: Depth-first search

Beitrag von Stefan1992 » 21. Jan 2016 12:32

Nein danke. Das beantwortet meine Frage.

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

Re: Depth-first search

Beitrag von Stefan1992 » 26. Jan 2016 00:56

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.
Dateianhänge
graph_example.png
graph_example.png (32.53 KiB) 302 mal betrachtet

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

Re: Depth-first search

Beitrag von Prof. Karsten Weihe » 26. Jan 2016 15:25

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

Antworten

Zurück zu „Effiziente Graphenalgorithmen“