Der Algorithmus von Tarjan (nach seinem Erfinder Robert Tarjan) dient in der Graphentheorie zur Bestimmung der starken Zusammenhangskomponenten (SZKn) eines gerichteten Graphen. Idee [ Bearbeiten | Quelltext bearbeiten] Die Grundidee des Algorithmus besteht darin, von einem Startknoten ausgehend eine Tiefensuche im Graphen durchzuführen. Die starken Zusammenhangskomponenten (SZKn) bilden dabei Teilbäume des Tiefensuchbaumes, die Wurzeln dieser Bäume heißen Wurzeln der Zusammenhangskomponenten. Die Knoten werden in der Reihenfolge, in der sie besucht werden, auf einem Stack abgelegt. Kehrt die Tiefensuche aus einem Unterbaum zurück, werden die Knoten wieder vom Stack genommen und ausgegeben, dabei wird jedes Mal entschieden, ob es sich bei dem Knoten um die Wurzel einer Zusammenhangskomponente handelt. Knoten für bootsführerschein binnen. Wenn ja, zeigt der Algorithmus an, dass die bisher ausgegebenen Knoten eine SZK bilden. Die Wurzeleigenschaft [ Bearbeiten | Quelltext bearbeiten] Beim Zurückkehren aus einem Unterbaum muss für jeden Knoten festgestellt werden, ob er die Wurzel einer Zusammenhangskomponente ist.
Besuche nun d, e # d: Initialisiert. Besuche nun a, e # d: a bereits besucht # e: Initialisiert. Besuche nun c, f # e: c bereits besucht # f: Initialisiert. Besuche nun g, i # g: Initialisiert. Besuche nun f, h # g: f bereits besucht # h: Initialisiert. Besuche nun j # j: Initialisiert. Besuche nun i # i: Initialisiert. Besuche nun f, g # i: f bereits besucht # i: g bereits besucht # i: Alle Kanten besucht # j: Alle Kanten besucht # h: Alle Kanten besucht # g: Alle Kanten besucht # f: i bereits besucht # f: Alle Kanten besucht # f: SZK gefunden! # f -> g -> h -> j -> i -> f # e: Alle Kanten besucht # d: Alle Kanten besucht # c: e bereits besucht # c: Alle Kanten besucht # b: Alle Kanten besucht # a: Alle Kanten besucht # a: SZK gefunden! # a -> b -> c -> d -> e -> a Literatur [ Bearbeiten | Quelltext bearbeiten] Robert Tarjan: Depth-first search and linear graph algorithms. In: SIAM Journal on Computing. Bd. 1 (1972), Nr. 2, S. 146–160.
lowlink); // Abfragen, ob v' im Stack ist. // Bei geschickter Realisierung in O(1). // (z. B. Setzen eines Bits beim Knoten beim "push" und "pop") elseif (v' in S) v. lowlink, v'); end if end for if (v. lowlink =) // Wurzel einer SZK print "SZK:"; repeat v':=; print v'; until (v' = v); Bemerkungen [ Bearbeiten | Quelltext bearbeiten] Aufwand: Die Prozedur tarjan wird für jeden Knoten genau einmal aufgerufen; die forall -Schleife betrachtet also jede Kante insgesamt höchstens zweimal. Des Weiteren muss aber nicht zu jedem Knoten eine Kante gehören. Die Laufzeit des Algorithmus ist also linear in der Anzahl der Kanten plus der Anzahl der Knoten von G. Beispiel-Implementierung des Algorithmus in Python [ Bearbeiten | Quelltext bearbeiten] # Hinweis: "SZK" bedeutet "Stark zusammenhängende Komponente (des Graphen)" class Knoten: __slots__ = [ 'kanten', 'index', 'szkindex', 'besucht'] def __init__ ( self, * kanten): self. kanten = kanten # Liste der Namen der Knoten zu denen dieser Knoten führt self.