Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Der Algorithmus von Tarjan (nach seinem Erfinder Robert Tarjan) dient in der Graphentheorie zur Bestimmung der starken Zusammenhangskomponenten (SZKn) eines Graphen.

[Bearbeiten] Idee

Die Grundidee des Algorithmus besteht darin, von einem Startknoten ausgehend eine Tiefensuche im Graphen durchzuführen. Die 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. Wenn ja, zeigt der Algorithmus an, dass die bisher ausgegebenen Knoten eine SZK bilden.

[Bearbeiten] Die Wurzeleigenschaft

Für den Algorithmus ist offenbar entscheidend, dass beim Zurückkehren aus einem Unterbaum für jeden Knoten festgestellt werden kann, ob er die Wurzel einer Zusammenhangskomponente ist. Dazu wird jedem Knoten v neben dem Tiefensuchindex v.dfs, welcher die Knoten in der Reihenfolge, in der sie bei der Tiefensuche "entdeckt" werden, durchnumeriert, ein Wert v.lowlink zugeordnet, wobei

v.lowlink := min {v'.dfs: v' ist von v erreichbar über beliebig viele Baumkanten, gefolgt von maximal einer weiteren Kante (v", v'), wobei v" und v' in derselben SZK liegen}

Es gilt nun: v ist die Wurzel einer Zusammenhangskomponente genau dann, wenn v.lowlink = v.dfs ist. v.lowlink kann während der Tiefensuche so berechnet werden, dass der Wert zum Zeitpunkt der Abfrage bekannt ist.

[Bearbeiten] Der Algorithmus in Pseudocode

Eingabe: Graph G = (V, E), Startknoten v0

max_dfs := 0  // Zähler für dfs
U := V        // Menge der unbesuchten Knoten
S := {}       // Stack zu Beginn leer
tarjan(v0)    // Aufruf mit Startknoten

procedure tarjan(v)
v.dfs := max_dfs;          // Tiefensuchindex setzen
v.lowlink := max_dfs;      // v.lowlink <= v.dfs
max_dfs := max_dfs + 1;    // Zähler erhöhen
S.push(v);                 // v auf Stack setzen
U := U \ {v};              // v aus U entfernen
forall (v, v') in E do     // benachbarte Knoten betrachten
  if (v' in U)
    tarjan(v');            // rekursiver Aufruf
    v.lowlink := min(v.lowlink, v'.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 := min(v.lowlink, v'.dfs);
  end if
end for
if (v.lowlink = v.dfs)     // Wurzel einer SZK
  print "SZK:";
  repeat
    v' := S.pop;
    print v';
  until (v' = v);
end if

[Bearbeiten] Bemerkungen

Aufwand: Die Prozedur tarjan wird für jeden Knoten nur einmal aufgerufen; die forall-Schleife betrachtet also jede Kante insgesamt höchstens zweimal. Die Laufzeit des Algorithmus ist also linear in der Anzahl der Kanten von G.
Der Algorithmus findet natürlich nur diejenigen SZKn, welche vom Startknoten aus erreichbar sind. Gegebenenfalls muss der Algorithmus also mehrmals mit unterschiedlichen Startknoten ausgeführt werden.