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
Depth-first search
Moderator: Effiziente Graphenalgorithmen
-
- Dozentin/Dozent
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Depth-first search
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?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?
KW
-
- Mausschubser
- Beiträge: 45
- Registriert: 20. Okt 2011 22:38
Re: Depth-first search
Nein danke. Das beantwortet meine Frage.
-
- Mausschubser
- Beiträge: 45
- Registriert: 20. Okt 2011 22:38
Re: Depth-first search
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.
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 (32.53 KiB) 412 mal betrachtet
-
- Dozentin/Dozent
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Depth-first search
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: 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.
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.Stefan1992 hat geschrieben: Als nächstes etwas schwieriger mit einem Beispiel: Findet die Tiefensuche jeden möglichen Pfad von einem Start- zu einem Zielknoten?
Klärt das Ihre Frage?
KW