Diskussion:Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten

-- 85.179.65.68

In Abschnitt: Die Wurzeleigenschaft

• Was soll der Nebensatz gefolgt von maximal einer weiteren Kante (v", v'), wobei v" und v' in derselben SZK liegen bei der Definition von v.lowlink? Konkreter: Die Definition verlangt einen Pfad von v nach v'. Wenn (v", v') eine Verlängerung des Pfades sein soll, dann ist die Konvention, dass man den Ursprung (also v' als Ende des Pfades) zuerst hinschreibt. Ist das gemeint, dann verstehe ich nicht, inwiefern dies die Definition beeinflusst: Gibt es eine Kante, dann ist es okay; gibt es kein, dann ist es ebenfalls okay (wg. maximal einer weiteren Kante). --Xlae (Diskussion) 12:02, 21. Jul. 2014 (CEST)

Korrektheit

mir ist völlig unklar, wie dieser Algorithmus die starken Zusammenhangskomponenten finden soll.

In einem Graphen wie z.B. A-->B findet er je nach Startpunkt die korrekten oder nicht korrekten starken Zusammenhangskomponenten.

Beginnt er mit A (=> A.dfs=0, A.lowlink=0) geht er in B (=> B.dfs=1, B.lowlink=1), stellt fest B.dfs=B.lowlink und gibt ( A,B ) als SZK aus, was natürlich totaler Humbug ist, weil es keinen Weg B-->A gibt, was es aber in einer SZK geben sollte.

• Mir ist das auch jedes Mal aufs neue unklar, in deinem Beispiel funktioniert der Algorithmus aber: Erreicht er den Knoten B und stellt fest, dass B.dfs = B.lowlink ist, so erkennt er B als Wurzel einer SZK, was ja korrekt ist. Die Prozedur tarjan, die rekursiv mit dem Argument B aufgerufen wurde, poppt nur bis zu diesem (also nur diesen) Knoten vom Stack und gibt ihn aus. Anschließend gibt die zuerst aufgerufene Prozedur noch den letzten auf dem Stack verbliebenen Knoten A als eigene SZK aus. Hoffe, die Verwirrung nicht nun perfekt. ;-) --Glotzfrosch 10:02, 23. Nov. 2007 (CET)

• Die Verwirrung könnte vom Unterschied von stark vs schwach im Bezug auf Zusammenhangskomponenten in gerichteten Graphen herrühren. In deinem Beispiel hat man die (starken) Zhken {A} und {B}. Startet der Algorithmus bei nun B, so findet er sofort {B}; die Rahmenschleife ganz außen stellt dann sicher, dass auch A noch besucht wird. Startet er hingegen bei A, dann geht der lowlink ein. --Xlae (Diskussion) 11:56, 21. Jul. 2014 (CEST)

Sehr schwer verständlich - Beispiel hinzufügen?

Tja, ehrlich gesagt verstehe ich in diesem Artikel nur Bahnhof. Könnte bitte jemand ein Beipiel einfügen? (oder zumindest einen Link zu einem Beispiel)

danke! (nicht signierter Beitrag von 139.18.178.18 (Diskussion) 11:47, 10. Mai 2011 (CEST))

Visualisierung Fehler?

Die Visualisierung ist super und hilft beim verstehen des Algorithmus. Nur eine Frage: Muesste der Knoten der zu Beginn mit 2,4 markiert wird nicht ganz am Ende auch 0,4 sein um Teil der linken SCC zu sein? Bzw. wenn nicht, woher weiss der Algorithmus, dass der Knoten zur SCC gehoert? Danke! (nicht signierter Beitrag von 207.151.221.248 (Diskussion) 20:04, 2. Jul 2014 (CEST))